走迷宫（Python）

走迷宫是回溯法的一个典型应用，本文主要通过Python来解决这个问题。

走迷宫问题

问题引入

【问题描述】有一个mn格的迷宫（表示有m行、n列），其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，输入这mn个数据和起始点、结束点（起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号）。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息（用-1表示无路）。

【输入形式】

第一行是两个数m，n（1< m, n< 15)，接下来是m行n列由1和0组成的数据，最后两行是起始点和结束点。

【输出形式】

所有可行的路径，输出时按照左上右下的顺序。描述一个点时用（x，y）的形式，除开始点外，其他的都要用“->”表示。如果没有一条可行的路则输出-1。

【样例输入】

5 4

1 1 0 0

1 1 1 1

0 1 1 0

1 1 0 1

1 1 1 1

1 1

5 4

【样例输出】

(1,1)->(1,2)->(2,2)->(2,3)->(3,3)->(3,2)->(4,2)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4)

(1,1)->(1,2)->(2,2)->(2,3)