Othello – Épreuve régionale 2007

Niveau 2

ENONCE

Othello (aussi appelé Reversi) est un jeu bien connu.

Il se joue à deux joueurs, sur un plateau 8*8. Les pions utilisés sont à double face : d'un côté blanc, de l'autre côté noir et chaque joueur utilise une couleur.

Les joueurs jouent chacun leur tour en posant un pion de leur couleur sur une case libre, de telle façon qu'entre ce pion posé et un autre pion de la même couleur, un pion au moins de la couleur adverse soit pris en tenaille, selon une ligne horizontale, verticale ou diagonale.

Le ou les pions pris sont alors retournés et ils prennent la couleur du preneur. La pose d'un pion peut prendre en tenaille des pions selon plusieurs directions, ils sont alors tous retournés.

Ainsi, par exemple, sur le schéma, lorsque le joueur noir place son pion sur la case marquée par un carré jaune, il retourne deux pions adverses comme indiqué dans le schéma suivant.

On vous donne un partie d'othello en cours. Vous avez les blancs, c'est à vous de jouer, et votre travail est de déterminer la position vous permettant de retourner le maximum possible de pions de l'adversaire.

ENTREE

Huit lignes de huit entiers chacune, séparés par un espace. Chaque entier vaut soit 0 pour indiquer que la case est vide, soit 1 pour indiquer un pion blanc, soit 2 pour indiquer un pion noir. On garantit que la grille en entrée contient au moins une case vide.

SORTIE

Les coordonnées de la position qui vous fait gagner le plus de pions : la ligne puis la colonne, séparées par un espace. On garantit que pour les données que l'on fournira au programme, la solution sera unique. Si vous ne pouvez prendre aucun pion, vous devez écrire en sortie un mot : "passe".

Contraintes d'exécution

Utilisation mémoire maximum
16000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 2 0
0 0 0 1 1 2 0 0
0 0 0 1 2 2 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
Exemple de sortie
1 7
Exemple d'entrée
2 2 2 0 0 0 0 0
2 2 2 1 0 0 0 0
2 2 2 0 0 0 1 0
2 2 2 1 1 1 0 0
2 2 2 1 1 1 0 0
2 2 2 1 0 0 0 0
2 2 2 1 0 0 0 0
2 2 2 1 0 0 0 0
Exemple de sortie
passe
Exemple d'entrée
1 0 2 0 0 2 1 2 
2 1 2 0 0 0 2 2 
1 1 0 1 2 0 2 0 
2 0 2 1 1 1 2 2 
2 1 0 2 1 2 1 2 
0 1 2 1 2 2 0 0 
2 2 0 1 2 0 1 2 
0 1 2 2 2 1 2 1
Exemple de sortie
6 5