#1303. 走迷宫

走迷宫

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

有一个nm\red{ n*m}格的迷宫(表示有n行m列),其中有可走的也有不可走的,如果用1\red{1}表示可以走,0\red{0}表示不可以走,文件读入这nm\red{n*m}个数据和起始点、结束点(起始点和结束点都是用两个数据来描述的,分别表示这个点的行号和列号)。

现在要你编程找出所有可行的道路,要求所走的路中没有重复的点,走时只能是上下左右四个方向。如果一条路都不可行,则输出相应信息(用-l表示无路)。

请统一用 左上右下的顺序拓展,也就是 (0\red{0},1\red{-1}),(1\red{-1},0\red{0}),(0\red{0},1\red{1}),(1\red{1},0\red{0})

输入格式

第一行是两个数n\red{n}m\red{m}( 1<nm<15\red{1 < n , m < 15} ),接下来是m行n列1\red{1}0\red{0}组成的数据,最后两行是起始点和结束点。

输出格式

所有可行的路径,描述一个点时用(x\red{x}y\red{y})的形式,除开始点外,其他的都要用“->”表示方向。

如果没有一条可行的路则输出1\red{-1}

样例

输入数据

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

输出数据

(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)

提示

有些情况很明显是无解的,如从起点到终点的矩形中有一行或一列都是为0\red{0}的,明显道路不通,对于这种情况要很快地“剪掉”多余分枝得出结论,这就是搜索里所说的“剪枝”。

从起点开始往下的一层层的结点,看起来如同树枝一样,对于其中的“枯枝”——明显无用的节点可以先行“剪掉”,从而提高搜索速度。

C++高级B1班01-搜索复习

未参加
状态
已结束
规则
IOI
题目
12
开始于
2024-9-22 16:00
结束于
2024-10-22 8:00
持续时间
712 小时
主持人
参赛人数
43