54 - ZJPCPC Sunny Cup 2006, Online Round - 1008
zzhang just bought a NDS, and he addicts to a game called "Polarium". The rule of the game is really simple: draw a line in the given grids and make sure the line doesn't intersect with itself. After this only operation, all the grids on the line flip - the original white grids become black, while the original black ones become white, except the grids on four borders (gray ones). The goal of the game is to make all the grids on every horizontal line in the same color - either black or white. (The gray ones will not be counted, referring to the third sample.)
Fortunately, the starting position and the ending position of a possible solution are given once you cannot solve the puzzle quickly. Now, zzhang asks you for help with this difficult problem.
There are several test cases. Each case begins with two integers N, M indicating the dimension of the grid. The following line contains 4 integers x1, y1, x2, y2 indicating the starting position and the ending position. The next N lines describe the grids, where 0 is a gray grid on the border, 1 is a black grid, and 2 is a white one.
Gray grids are always on the border, while all the white and black grids are not.
Proceed until a case with N = M = 0, which should not be processed.
For each test case, print a single integer in a line indicating the length (how many grids it contains) of the line drawn. Print an exact path of the line in the next line. Any feasible path is OK if there exists more than one solution. The path contains at least 2 grids (the starting grid and the ending grid). Refer to the sample output for more information.
Note: there is always at least one solution for the puzzle with given information. Each two adjacent grids on the drawn line must share a border, which means the line can't go diagonally.
7 7 1 1 5 5 0000000 0111220 0221220 0221220 0221220 0221110 0000000 5 4 1 2 3 2 0000 0120 0220 0210 0000 0 0
9 1 1 -> 1 2 -> 1 3 -> 2 3 -> 3 3 -> 4 3 -> 5 3 -> 5 4 -> 5 5 5 1 2 -> 1 3 -> 2 3 -> 3 3 -> 3 2
Author: ZHANG, Zheng