J8 习题-4 逃生轨迹

题目描述

一个有 $n$行、$m$列的迷宫，其中有可走的和不可走的格子，用 $1$ 表示该格子可以走，$0$ 表示该格子不可以走。 现在知道迷宫的形态和起始点、结束点，如果移动时只能走上下左右四个方向。 请找出所有可行的道路，注意：一条逃生轨迹不能重复走任何一个点。如果没有可行解，则输出 -1 。 输出的轨迹，请按左、上、右、下的顺序拓展，即 $(0,-1),(-1,0),(0,1),(1,0)$。

输入格式

共 $n+2$ 行： 第一行是两个数$n,m$； 接下来是 $n$ 行 $m$ 列，由 1 和 0 组成的迷宫形态； 最后两行，分别表示起始点和结束点。

输出格式

输出所有可行的路径，描述一个点时用 $(x,y)$ 的形式（具体格式参考样例）； 除了点外，其他的都要用 -> 表示方向。 如果没可行的路，则输出 -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)

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据：$1\le n,m \le 15$ 。