[ED004] Jogo do Galo

O problema

Quem não conhece o famoso jogo do galo? Neste problema é-lhe pedido que dado um tabuleiro de um jogo do galo, com algumas jogadas possivelmente já feitas, o analise e diga se algum dos jogadores ganhou. Para complicar um pouco as coisas, imagine uma generalização do jogo, sempre num tabuleiro quadrado, mas que pode ser de dimensão diferente de 3x3. Tal como no original, os jogadores jogam à vez e ganham se conseguirem preencher completamente uma linha, uma coluna ou uma diagonal.

Input

Na primeira linha vem um número N, indicando a dimensão do tabuleiro (que é sempre quadrado).

Seguem-se N Linhas, cada uma com N caracteres ('X', 'O' ou '.') indicando o estado actual do jogo.

Tal como esperado, X e O representam uma casa ocupada por um dos dois jogadores, e . representa uma casa vazia.

Pode assumir que será sempre um estado de jogo válido (por exemplo, nunca acontecerá haver dois vencedores).

Output

• Ganhou o X - Caso o jogador X consiga ter preenchido uma linha, coluna, ou diagonal
• Ganhou o O - Caso o jogador O consiga ter preenchido uma linha, coluna, ou diagonal
• Empate - Nenhum dos jogadores ganhou, e o jogo já terminou
• Jogo incompleto - Nenhum dos jogadores ganhou, mas o jogo ainda não terminou

Exemplo de input/output

3
...
...
...

4
XXXX
OOO.
....
....

2
XO
O.

3
XOX
OOX
XXO

Última actualização: