프로그램 명: coci_rotacije(special judge)
제한시간: 1 초
[요약] n * m 행렬이 주어지고 각 셀에는 1 에서 n 까지의 수가 랜덤하게 주어져 있다. 할 수 있는 동작은 이 중 2*2 행렬을 시계 방향으로 90 도 회전하는 동작을 할 수 있다.
이 동작으로 수가 차례대로 정렬되도록 하는 것이 문제이다.
회전 동작을 최적으로 할 필요는 없고 주어진 데이터에서 답이 유일하지않을 수 있지만 존재한다는 것은 보장된다.
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:
-
The unlocking mechanism is a table with R rows and C columns. Each cell contains a unique
positive integer between 1 and R*C, inclusive. At first glance, the numbers appear to be
ordered randomly.
-
The mechanism contains cogwheels which Diana can use to rearrange the table cells. In one
move, she can rotate any 2-by-2 group of adjacent cells clockwise by 90 degrees.
-
The gate will be unlocked when the numbers are rearranged in sorted row-major order (the
upper left cell must contain 1, the cell to the right of it 2, and so on until the lower right cell,
which must contain R*C).
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.
입출력 예
input
2 3
3 2 6
1 4 5
output
1 1
1 2
input
3 3
1 2 3
4 6 9
7 5 8
output
2 2
input
2 4
1 2 7 3
5 6 8 4
output
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.
출처:CROATIAN olympiad 2013
[질/답]
[제출 현황]
[푼 후(0)]