시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 256 MB | 3 | 2 | 2 | 66.667% |
The famous archaeologist Diana Jones has discovered a secret passageway leading to hidden treasure near Nowhere, Kansas. The passageway is blocked by a stone gate which has an ancient unlocking mechanism chiselled into it. Fortunately, she has immediately recognized the chiselled symbols:
For example, for the initial arrangement shown in the first picture, two moves are sufficient to unlock the mechanism:
Write a program that, given the initial arrangement of cells, finds a sequence of moves that unlocks the mechanism. The number of moves needn't be optimal, however it must not exceed 100 000.
The first line of input contains the two positive integers R and C (2 ≤ R ≤ C ≤ 25).
Each of the following R lines contains C positive integers Zij (1 ≤ Zij ≤ R*C), the numbers chiselled into the corresponding mechanism cells, which describes the initial arrangement.
The output must contain the required sequence of moves, one per line. For each move, output two positive integers M and N (1 ≤ M ≤ R-1, 1 ≤ N ≤ C-1) representing the row and column index of the upper left cell in the 2-by-2 group rotated in that move.
Note: For the given input data, a solution, not necessarily unique, will always exist.
2 3 3 2 6 1 4 5
1 1 1 2
3 3 1 2 3 4 6 9 7 5 8
2 2
2 4 1 2 7 3 5 6 8 4
1 3 1 3 1 3
Clarification of the first example: According to the picture in the problem description, the initial arrangement can be ordered in two moves: we first rotate the group with the upper left corner in row 1 and column 1, and then the group with the upper left corner in row 1 and column 2.