Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: 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.
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 Output Print your solution as follows. The first line contains an integer n. Each of the next n lines is in the format “ _{−1},c_{k}_{−1}) (r_{k},c_{k})”where ( _{−1}, c_{k}_{−1}) is a path through the sand, and (r_{0}, c_{0}) and (r, _{k}c) are two fictional squares outside the sand and immediately next to (_{k}r_{1}, c_{1}) and (r_{k}_{−1}, c_{k}_{−1}), respectively.If multiple solutions exist, you may print any one. Sample Input 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 0 Sample Output 6 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 |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator