Zen Puzzle Garden
Description
Zen Puzzle Garden is a single-player game in which the player has to control a little monk who must endeavor to rake all of the sand in a Japanese rock garden. Figure 11 shows three screenshots of the game.
| (a) | (b) | (c) |
Figure 11: Screenshots of Zen Puzzle Garden
The sand in the garden is divided into a rectangular grid of squares. Some of the squares are occupied by rocks. As shown in Figure 11(a), before he starts, the monk stands outside the sand. Then he repeatedly walks along a path through the sand consisting of adjacent squares and rakes every square in the path. Adding to the complexity, he cannot walk over the squares that have already been raked or that are occupied by rocks. Furthermore, he is not allowed to change direction unless he cannot move ahead any more. Figure 11(b) illustrates that the monk has raked some squares, and he now must walk right until he exits the sand. To complete the game, the monk must rake all sand-covered squares and not be “trapped” in the sand when he finishes, as shown in Figure 11(c).
Given a solvable puzzle, find a solution to it.
Input
The input contains a single test case describing a solvable puzzle. The first line contains two integers r and c (2 ≤ r, c ≤ 12). The next r lines, each containing c integers, give an r × c 0-1 matrix describing the sand in the garden. A 0 indicates a sand-covered square; a 1 indicates a rock-occupied square. All squares are not occupied by rocks.
Output
Print your solution as follows. The first line contains an integer n. Each of the next n lines is in the format
“k: (r0,c0) (r1,c1) ⋯ (rk−1,ck−1) (rk,ck)”
where (r1, c1), (r2, c2), …, (rk−1, ck−1) is a path through the sand, and (r0, c0) and (rk, ck) are two fictional squares outside the sand and immediately next to (r1, c1) and (rk−1, ck−1), respectively.
If multiple solutions exist, you may print any one.
5 5
0 0 0 0 0
0 0 0 0 0
0 1 0 0 0
0 0 0 1 0
0 0 0 0 06
7: (0,1) (1,1) (2,1) (3,1) (4,1) (5,1) (6,1)
7: (0,2) (1,2) (2,2) (2,3) (2,4) (2,5) (2,6)
4: (4,6) (4,5) (5,5) (6,5)
8: (6,2) (5,2) (4,2) (4,3) (3,3) (3,4) (3,5) (3,6)
5: (0,3) (1,3) (1,4) (1,5) (1,6)
4: (6,3) (5,3) (5,4) (6,4)Source
PKU Campus 2008 (POJ Founder Monthly Contest – 2008.05.10), xfxyjwf