COI '12 #2 Rotacije

View as PDF

Submit solution

Points: 30 (partial)
Time limit: 0.5s
Memory limit: 256M

Problem types

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 \times 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 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 \times 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.

Input Specification

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_{i,j} (1 \le Z_{i,j} \le R \times C), the numbers chiselled into the corresponding mechanism cells, which describes the initial arrangement.

Output Specification

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.

Scoring

In test data worth a total of 40 points, R \times C \le 9.

In test data worth a total of 40 points, R = 2.

In test data worth a total of 60 points, at least one of the two constraints above will hold.

Sample Input 1

2 3
3 2 6
1 4 5

Sample Output 1

1 1
1 2

Explanation for Sample Output 1

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.

Sample Input 2

3 3
1 2 3
4 6 9
7 5 8

Sample Output 2

2 2

Sample Input 3

2 4
1 2 7 3
5 6 8 4

Sample Output 3

1 3
1 3
1 3

Comments

There are no comments at the moment.