| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 158 | 126 | 114 | 79.167% |
The princess of Nlogonia keeps her pearl collection in a square jewelry case made up of $N$ columns, each column containing $N$ small boxes. She places a different number of pearls in each box, and arranges the box so that in each column, from top to bottom, the boxes contain an increasing number of pearls and in each row, from left to right, the boxes also contain an increasing number of pearls.
The princess suspects that her little sister, who is very mischievous, is messing with her things in her games. In particular, the princess suspects that her jewelry case has been rotated 90ドル$ degrees clockwise, possibly multiple times.
Figure (a) below shows an example of the original arrangement of a 4ドル \times 4$ case. Figure (b) shows the case rotated clockwise, 90ドル$ degrees, once.
Given the number of pearls in each box, write a program to determine the smallest number of 90ドル$-degree counterclockwise rotations that are necessary to return the jewelry case to its original state.
The first line of the input contains an integer $N,ドル the number of rows and columns in the case (2ドル ≤ N ≤ 50$). Each of the following $N$ lines contains $N$ integers $K_{i,j},ドル the number of pearls in the box in row $i$ and column $j$ (0ドル ≤ K_{i,j} ≤ 10^5,ドル for 1ドル ≤ i ≤ N$ and 1ドル ≤ j ≤ N$). In the input, the rows are given from top to bottom, and the columns are given from left to right.
Your program should output a single line containing only one integer $R$ (which can be 0ドル,ドル 1ドル,ドル 2ドル,ドル or 3ドル$), the smallest number of times the jewelry case must be rotated counterclockwise to return to its original state.
4 15 9 7 3 16 14 10 4 20 17 11 6 25 22 19 12
1
This example corresponds to the example in the statement. It is necessary to rotate the case counterclockwise once.
3 300 250 150 280 200 140 240 190 130
2
It is necessary to rotate the case counterclockwise twice.
2 2 4 1 3
3
It is necessary to rotate the case counterclockwise three times.