题解 | 迷宫问题

import copy
# 接受输入
h, w = map(int, input().split())
maps = []
for i in range(h):
    maps.append(list(map(int, input().split())))
# 定义回归迭代
def next_step(last_step, now_step, maps,steps):
    h = len(maps) - 1
    w = len(maps[0]) - 1
    if now_step == [h, w]:
        return True
    next_xy = copy.copy(now_step)
    # 分四类-1
    next_xy[0] = now_step[0] - 1  # 向上走一步
    if next_xy[0] < 0 or next_xy[0] == last_step[0]:
        pass  # 超边界或返货上一步，直接跳过
    elif maps[next_xy[0]][next_xy[1]] == 1:
        pass  # 碰墙壁
    elif next_step(now_step, next_xy, maps,steps):
        steps.append(next_xy)
        return True
    # 分四类-2
    next_xy = copy.copy(now_step)
    next_xy[0] = now_step[0] + 1  # 向下走一步
    if next_xy[0] > h or next_xy[0] == last_step[0]:
        pass  # 超边界或返货上一步，直接跳过
    elif maps[next_xy[0]][next_xy[1]] == 1:
        pass  # 碰墙壁
    elif next_step(now_step, next_xy, maps,steps):
        steps.append(next_xy)
        return True
    # 分四类-3
    next_xy = copy.copy(now_step)
    next_xy[1] = now_step[1] - 1  # 向左走一步
    if next_xy[1] < 0 or next_xy[1] == last_step[1]:
        pass  # 超边界或返货上一步，直接跳过
    elif maps[next_xy[0]][next_xy[1]] == 1:
        pass  # 碰墙壁
    elif next_step(now_step, next_xy, maps,steps):
        steps.append(next_xy)
        return True
    # 分四类-4
    next_xy = copy.copy(now_step)
    next_xy[1] = now_step[1] + 1  # 向右一步
    if next_xy[1] > w or next_xy[1] == last_step[1]:
        pass  # 超边界或返货上一步，直接跳过
    elif maps[next_xy[0]][next_xy[1]] == 1:
        pass  # 碰墙壁
    elif next_step(now_step, next_xy, maps,steps):
        steps.append(next_xy)
        return True
    # 无路可走返回
    return False

# 主函数
steps = []  # 初始化集合
last_step = [0, 0]  # 初始化第一步
h -= 1
w -= 1
# 分两个方向分析

# 分2个方向前进
now_step = copy.copy(last_step)
# 方向一，向下一步
now_step = copy.copy(last_step)
now_step[0] += 1
if maps[now_step[0]][now_step[1]] == 1:
    pass
elif next_step(last_step, now_step, maps,steps):
    steps.append(now_step)
# 方向二，向右一步
now_step = copy.copy(last_step)
now_step[1] += 1
if maps[now_step[0]][now_step[1]] == 1:
    pass
elif next_step(last_step, now_step, maps,steps):
    steps.append(now_step)
# 结果整理
steps.append(last_step)
steps = steps[::-1]
# 结果输出
for i in range(len(steps)):
    print('('+str(steps[i][0])+','+str(steps[i][1])+')')