Le Gomoku est un jeu de plateau à deux joueurs, dans lequel pour gagner, chaque joueur doit réussir à aligner 5 pions sur des cases consécutives d'un plateau, horizontalement, verticalement ou en diagonale. Le plateau est une grille carrée, de dimension quelconque.
Ecrivez un programme qui lit en entrée le contenu d'une partie de Gomoku, et détermine si l'un des joueurs a gagné.
Limites de temps et de mémoire (Python)
- Temps : 1 s sur une machine à 1 GHz.
- Mémoire : 1 000 ko.
Contraintes
- 1 <= N <= 40, où N est le nombre de lignes/colonnes du plateau utilisé pour la partie.
Entrée
La première ligne de l'entrée contient un entier
N : le nombre de colonnes et de lignes du plateau de Gomoku.
Chacune des N lignes suivantes contient N entiers, séparés par des espaces, correspondant au contenu des cases d'une ligne du plateau. L'entier vaut 0 si la case est vide, 1 si elle contient un pion du joueur 1, et 2 pour un pion du joueur 2.
Sortie
Votre programme doit afficher une ligne contenant un entier : le numéro du joueur gagnant (1 ou 2), ou 0 si aucun des joueurs n'a aligné 5 pions.
Exemple
entrée :
6
0 0 2 0 1 0
0 1 2 2 2 1
0 0 2 0 1 0
0 0 2 1 0 0
0 0 1 0 0 0
0 1 0 0 0 0
sortie :
1