All submissions for this problem are available.
Recently, with the release of the ultimate computing device bytePad, a platform game with the simple name "Rotation Puzzle" immediately became a phenomenon among Bytelandians. The game is extremely simple, yet quite additive. Here's the rule:
Given a MxN rectangular grid in which each cell contains a unique number from 1 to MxN. In each step, the player can pick any 2x2 subgrid and perform a rotation (whether clockwise or counterclockwise).
The task is to transform from the initial grid to the final configuration, using as few steps as possible.
The final configuration is the configuration
1 2 ... n
n+1 n+2 ... 2n
... ... ... ...
(m-1)n+1 (m-1)n+2 ... mn
You may have guessed why this game is addictive: it requires a tremendous visualization skill!
The first line contains a number T (about 5000), which is the number of test cases. Each test case has the following form.
The first line contains two numbers M and N (2 <= M, N <= 34).
The next M lines contains the description of the grid.
Each test case's input is separated by a blank line.
It is guaranteed that each input data has a solution.
For each test case, output the result in the following format.
The first line contains a number K, the number of steps you need to solve the puzzle. K must not exceed 10000.
Each line of the next K lines contain three numbers c, i, j (c=0 or c=1, 1<=I < M, 1 <= J < N). (i,j) is the top-left coordinate of the 2x2 square that is need to be rotated. c=1 if the rotation if clockwise and c=0 if the rotation is counter-clockwise.
Prints a blank link after each test case's output.
2 2 3 1 5 2 4 6 3 2 3 5 6 2 1 4 3 etc.
Sample output1 0 1 2 2 1 1 1 0 1 2 etc.
|Time Limit:||0.15 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.