Problema das transformações (USACO)

Tradução de Transformations da USACO (http://ace.delos.com/usacoprob2?a=pbvbeOWRbRk&S=transform).

Dificuldade Única

Um padrão quadrado tamanho NxN (1<=N<=10), composto por quadrados brancos e pretos, pode ser transformado em outro padrão quadrado. Escreva um programa capaz de reconhecer a menor transformação ao qual o padrão original foi submetido dada a seguinte lista de possiveis transformações:

• #1: Rotação de 90 graus: o padrão foi rotacionado 90 graus no sentido horário.
• #2: Rotação de 180 graus: o padrão foi rotacionado 180 graus no sentido horário.
• #3: Rotação de 270 graus: o padrão foi rotacionado 270 graus no sentido horário.
• #4: Reflexão: o padrão foi refletido horizontalmente (transformado em um espelho de si mesmo a partir de uma linha vertical no meio do padrão).
• #5: Combinação: o padrão foi refletido horizontalmente e então submetido a uma das rotações de #1 a #3.
• #6: Sem mudanças: o padrão original não foi alterado.
• #7: Transformação inválida: o novo padrão não foi obtido por qualquer dos métodos anteriores.

No caso de mais de uma transformação gerar o resultado, escolha como resposta aquela que tiver o menor dos valores.

Formato de entrada

• Linha 1: Um único inteiro, N.
• Linha 2..N+1: N linhas de N caracteres ('@' ou '-'); este é o padrão antes da transformação.
• Linha N+2..2*N+1: N linhas de N caracteres ('@' ou '-'); este é o padrão depois da transformação.

Nome do arquivo de entrada: transform.in.

Exemplo de entrada

3
@-@
---
@@-
@-@
@--
--@

Formato de saída

Uma única linha contendo um número de 1 a 7 (conforme descrito acima) que classifica a transformação requerida para da representação "antes" se chegar à representação "depois".

Nome do arquivo de entrada: transform.out.

Exemplo de saída

1