\(7^{th}\) round (Croatian Olympiad in Informatics), April \(6^{th}\), 2013

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:
1. 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.
2. 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.
3. The gate will be unlocked when the numbers are rearranged in sorted r\(ow-ma\)jor 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:
3
2
6
1
4
5

→
1
3
6
4
2
5

→
1
2
3
4
5
6

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.

In test data worth a total of 40 points, \(R*C\) will be at most 9.
In test data worth a total of 40 points, R will be equal to 2.
In test data worth a total of 60 points, at least one of the two constraints above will hold.
\(7^{th}\) round (Croatian Olympiad in Informatics), April \(6^{th}\), 2013

The first line of input contains the two positive integers R and C (\(2 \le R \le C \le 25\)).
Each of the following R lines contains C positive integers Z_{ij} (\(1 \le Z_{ij} \le 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 \le M \le R-1\), \(1 \le N \le 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.

생성자가 기록되지 않았습니다.

출처 COCI 2012/2013 Olympiad