Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
54 - ZJPCPC Sunny Cup 2006, Online Round - 1008
Polarium

Time Limit: 5 Seconds      Memory Limit: 32768 KB      Special Judge

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.

Input

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.

Constraints:

  • N is an integer in the range of 4 to 9, inclusive.
  • M is an integer in the range of 4 to 9, inclusive.
  • x1, x2 are both integers in the rage of 0 to N-1, inclusive.
  • y1, y2 are both integers in the rage of 0 to M-1, inclusive.

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.

Output

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.

Sample Input

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

Sample Output

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


Submit    Status