# 描述
# 定义一个二维数组 N*M ，如 5 × 5 数组下所示：
# int maze[5][5] = {
# 0, 1, 0, 0, 0,
# 0, 1, 1, 1, 0,
# 0, 0, 0, 0, 0,
# 0, 1, 1, 1, 0,
# 0, 0, 0, 1, 0,};
# 它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路。
# 数据范围： 2≤n,m≤10 ， 输入的内容只包含 0≤val≤1
# 输入描述：
# 输入两个整数，分别表示二维数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。
# 输出描述：
# 左上角到右下角的最短路径，格式如样例所示。
# 示例1
# 输入：
# 5 5
# 0 1 0 0 0
# 0 1 1 1 0
# 0 0 0 0 0
# 0 1 1 1 0
# 0 0 0 1 0
# 输出：
# (0,0)
# (1,0)
# (2,0)
# (2,1)
# (2,2)
# (2,3)
# (2,4)
# (3,4)
# (4,4)
def func(i, j, pos=[(0, 0)]):# 方法1if i == m - 1 and j == n - 1:for p in pos:print(p)return 1if j + 1 < n and a[i][j + 1] == 0: # 向右if (i, j + 1) not in pos:func(i, j + 1, pos + [(i, j + 1)])if j - 1 > 0 and a[i][j - 1] == 0: # 向左if (i, j - 1) not in pos:func(i, j - 1, pos + [(i, j - 1)])if i + 1 < m and a[i + 1][j] == 0: # 向下if (i + 1, j) not in pos:func(i + 1, j, pos + [(i + 1, j)])if i - 1 > 0 and a[i - 1][j] == 0: # 向上if (i - 1, j) not in pos:func(i - 1, j, pos + [(i - 1, j)])def dfs(i, j):# 方法2# 用dx和dy分别来表示：向左， 向右， 向上， 向下dx = [0, 0, -1, 1]dy = [-1, 1, 0, 0]if i == m - 1 and j == n - 1:for pos in route:print('(' + str(pos[0]) + ',' + str(pos[1]) + ')')returnfor k in range(4):x = i + dx[k]y = j + dy[k]if 0 <= x < m and 0 <= y < n and map1[x][y] == 0:map1[x][y] = 1route.append((x, y))dfs(x, y)# 如果我们无法到达指定终点，则需要沿原路返回,再把标记过的路去掉：map[x][y]=0，route.pop(),# 直到到达当初的分岔路口，进入下一次选择。map1[x][y] = 0route.pop()else:returnif __name__ == '__main__':m = 5n = 5a = [[0, 0, 0, 0, 1],[0, 1, 1, 0, 0],[0, 1, 0, 0, 1],[0, 0, 1, 0, 0],[0, 1, 0, 1, 0]]func(0, 0)map1 = a.copy()route = [(0, 0)]map1[0][0] = 1dfs(0, 0)
