Problem1726--走迷宫 maze [2*+]

1726: 走迷宫 maze [2*+]

[Creator : ]
Time Limit : 1 sec  Memory Limit : 128 MB

Description

有一个m行n列的迷宫,迷宫中有的地方可以走,有的不可以走,1表示能通过,0表示不能。现在要求求出所有可行的道路,其中没有重复的点,只能上下左右四个方向。如果没有路可以走的话,就输出-1.

Input
【输入】 第一行是两个数m,n
(2<=m,n<=17),
接下来是m行n列由1和0组成的数据,最后两行是起始点和结束点。

Output
【输出】 所有可行的路径,描述一个点时用(x,y)的形式,除开始点外,其他的都要用“一>”表示方向。 如果没有一条可行的路则输出-1。

Sample Input

【样例】	maze.in
			5 6
			1 0 0 1 0 1
			1 1 1 1 1 1 
			0 0 1 1 1 0
			1 1 1 1 1 0
			1 1 1 0 1 1
			1 1
			5 6 

Sample Output

maze.out
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6) 

Hint
【提高思考】:若本题要求输出最短的一条路则应使用宽搜

Source/Category