Canadian Computing Olympiad: 2017 Day 2, Problem 3
You are given a rectangular grid of numbered tiles, with no empty spaces. This grid can only be manipulated using a sequence of shift operations. A shift involves either moving an entire row left or right by some number of units, or moving an entire column up or down by some number of units. Tiles which move outside of the rectangular boundaries wrap around to the opposite side of the grid. For example, in the grid
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
a vertical shift downwards by one applied to the second column has the following result:
0 13 2 3
4 1 6 7
8 5 10 11
12 9 14 15
Notice that a left shift by units is the same as a right shift by
units. Similarly, an upward shift by
units is a downward shift by
units. Thus, without loss of generality, we will restrict the shift directions to be only to the right or down.
In a grid with rows and
columns, there are
tiles in total. You may assume that the tiles are numbered with distinct integers from
to
.
You may have noticed that in the first example given above, the tiles are in a very organized
formation. We call such arrangements solved. That is, a grid of tiles is solved when the first row
contains the numbers from to
in order, the second row has the numbers from
to
in order, and so on, with the last row having the number
to
in order.
Find a sequence of shift operations that restores a scrambled grid to a solved state.
Input Specification
The first line will contain two space-separated integers and
(
). The next
lines will contain
space-separated integers, representing the grid.
Note that both and
will always be even, and there will be a solution requiring at most
shift operations.
For 5 of the available 25 marks, .
For an additional 10 of the available 25 marks, the puzzle is solvable in at most 2 moves.
Output Specification
Output any sequence of moves that solves the puzzle, in the following format:
- The first line of output should contain a single integer
, representing the number of moves in the sequence.
- The next
lines should be either of the form 1
representing a right shift of the
row by
, or of the form 2
representing a down shift of the
by
.
Sample Input 1
2 4
4 2 3 0
1 5 6 7
Output for Sample Input 1
2
2 1 1
1 1 1
Explanation for Output for Sample Input 1
We shift the first column down by one to obtain
1 2 3 0
4 5 6 7
then shift the first row right by one to reach the state
0 1 2 3
4 5 6 7
which is solved.
Sample Input 2
4 2
2 3
5 0
4 1
6 7
Output for Sample Input 2
7
1 1 1
2 1 1
1 2 1
1 3 1
2 1 2
1 1 1
2 1 1
Explanation for Output for Sample Input 2
The sequence of shifts, starting from the input is:
2 3 3 2 6 2 6 2 6 2 1 2 2 1 0 1
5 0 -> 5 0 -> 3 0 -> 0 3 -> 0 3 -> 4 3 -> 4 3 -> 2 3
4 1 4 1 5 1 5 1 1 5 6 5 6 5 4 5
6 7 6 7 4 7 4 7 4 7 0 7 0 7 6 7
Comments
Equivalent to this problem.