4600: 走迷宫 II
[Creator : ]
Description
有一个 $n*m$ 格的迷宫(表示有 $n$ 行、$m$ 列),其中有可走的也有不可走的,如果用 $1$ 表示可以走,$0$ 表示不可以走,文件读入这 $n*m$ 个数据和起始点、结束点,起始点和结束点都是用两个数据来描述的,分别表示这个点的行号和列号。
现在要你编程找出所有可行的道路,要求所走的路中没有重复的点,走时只能是上下左右四个方向。如果一条路都不可行,则输出相应信息(用 $-1$ 表示无路)。
请统一用 左上右下 的顺序拓展,也就是 $(0,\ -1),\ (-1,\ 0),\ (0,\ 1),\ (1,\ 0)$。
现在要你编程找出所有可行的道路,要求所走的路中没有重复的点,走时只能是上下左右四个方向。如果一条路都不可行,则输出相应信息(用 $-1$ 表示无路)。
请统一用 左上右下 的顺序拓展,也就是 $(0,\ -1),\ (-1,\ 0),\ (0,\ 1),\ (1,\ 0)$。
Input
第一行是两个数 $n,\ m\ (1 < n,\ m < 15)$。
接下来是 $n$ 行 $m$ 列由 $1$ 和 $0$ 组成的数据,
最后两行是起始点和结束点。
接下来是 $n$ 行 $m$ 列由 $1$ 和 $0$ 组成的数据,
最后两行是起始点和结束点。
Output
所有可行的路径,描述一个点时用 $(x,\ y)$ 的形式,除开始点外,其他的都要用 “->” 表示方向。
如果没有一条可行的路则输出 $-1$。
如果没有一条可行的路则输出 $-1$。
Sample 1 Input
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 1 Output
(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)