Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Zen Puzzle Garden
Time Limit: 20000MSMemory Limit: 131072K
Total Submissions: 305Accepted: 75
Case Time Limit: 6000MSSpecial Judge


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.


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.


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.

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

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)


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

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator