Estojo de Joias

#25
Made by: Ricardo Anido
1024MB
0.1s

A princesa da Nlogônia guarda sua coleção de pérolas em um estojo de jóias quadrado composto de N colunas, cada coluna com N caixinhas. Ela coloca um número diferente de pérolas em cada caixinha, e organiza o estojo de forma que em cada coluna, de cima para baixo, as caixinhas contenham números crescentes de pérolas e que em cada linha, da esquerda para a direita, as caixinhas também contenham números crescentes de pérolas.

A princesa desconfia que sua irmã pequena, que é muito sapeca, esteja mexendo nas suas coisas em suas brincadeiras. Em particular, a princesa desconfia que seu estojo de jóias tenha sido rotacionado de 90 graus no sentido horário, possivelmente múltiplas vezes.

A figura (a) abaixo mostra um exemplo da organização original de um estojo 4 × 4. A figura (b) mostra o estojo rotacionado no sentido horário, de 90 graus, uma vez.

(a)

3 4 6 12
7 10 11 19
9 14 17 22
15 16 20 25

(b)

15 9 7 3
16 14 10 4
20 17 11 6
25 22 19 12

Dados os números de pérolas em cada caixinha, escreva um programa para determinar qual o menor número de rotações de 90 graus no sentido anti-horário que são necessárias para fazer com que o estojo de jóias volte para o estado original.

Input

A primeira linha da entrada contém um inteiro $N$ , o número de linhas e colunas do estojo $(2 ≤ N ≤ 50)$. Cada uma das $N$ linhas seguintes contém $N$ inteiros $K_{i,j}$ , a quantidade de pérolas da caixinha na linha $i$ e coluna $j$ $(0 ≤ K_ {i,j} ≤ 10^5 , para 1 ≤ i ≤ N e 1 ≤ j ≤ N )$. Na entrada, as linhas são dadas de cima para baixo, e as colunas são dadas da esquerda para a direita.

Output

Seu programa deve produzir uma única linha contendo apenas um inteiro $R$ (que pode ser 0, 1, 2 ou 3), o menor número de vezes que o estojo de jóias deve ser rotacionado no sentido anti-horário para retornar ao estado original.

Input Example
Output Example 
4
15 9 7 3
16 14 10 4
20 17 11 6
25 22 19 12

1

Explanation 1:
Este exemplo corresponde ao exemplo do enunciado. E necessário rotacionar o estojo no sentido anti-horário uma vez. 

3
300 250 150
280 200 140
240 190 130

2

Explanation 2:
E necessário rotacionar o estojo no sentido anti-horário duas vezes. 

2
2 4
1 3

3

Explanation 3:
É necessário rotacionar o estojo no sentido anti-horário três vezes.