题解 | #迷宫问题#

# 2024年1月20日  周四   上午9:56  晴
# wujie
# maze = 迷宫
# pos= 位置

### 此题不难，用的是递归方法，需要多看几遍
########### 得空的时候研究一下，这个题还有没有其他的解法
m, n = list(map(int, input().split()))  # 输入矩阵的行和列，m表示行，n表示列
migong = []  # 用来存储路径

# 输入迷宫，即地图
for i in range(m):
    migong.append(list(map(int, input().split())))

# print('>>>migong=',migong)
# 迷宫已构建好，接下来就是走迷宫

# 只能横着走或竖着走，横着走，包括向左或者向右，竖着走包括向上或者向下，DFS要追求循环的顺序是顺时针，即右下左上
# 走迷宫，即遍历符合条件的点，遍历顺序为顺时针，即右->下->左->上
def walk(i, j, pos=[(0, 0)]):  # pos用来存储路径
    if (
        j + 1 < n and migong[i][j + 1] == 0
    ):  # 向右    # 如果j+1小于n，并且此位置maze[i][j+1]==0，表示此位置是路，不是墙。
        if (i, j + 1) not in pos:  # 如果(i,j+1)没有走过
            walk(
                i, j + 1, pos + [(i, j + 1)]
            )  # 那么走一下(i,j+1)这条路{走一下这条路，就是调用一下他自己，但是要记得改变参数}，并把此路添加至路径列表pos中
    if i + 1 < m and migong[i + 1][j] == 0:  # 向下
        if (i + 1, j) not in pos:
            walk(i + 1, j, pos + [(i + 1, j)])
    if j - 1 >= 0 and migong[i][j - 1] == 0:  # 向左，往回走了？
        if (i, j - 1) not in pos:
            walk(i, j - 1, pos + [(i, j - 1)])
    if i - 1 >= 0 and migong[i - 1][j] == 0:  # 向上，往回走了？
        if (i - 1, j) not in pos:
            walk(i - 1, j, pos + [(i - 1, j)])
    if (i, j) == (m - 1, n - 1):  # 迷宫右下角的点，即递归的出口
        for p in pos:
            print("(" + str(p[0]) + "," + str(p[1]) + ")")


walk(0, 0)