题解 | 迷宫问题

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):
    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):
        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):
        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):
        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):
        return True
    # 无路可走返回
    return False

# 主函数
steps = []  # 初始化集合
last_step = [0, 0]  # 初始化第一步
steps.append(last_step)
h -= 1
w -= 1
while 1:
    # 分四个方向前进
    now_step = copy.copy(last_step)
    # 方向一，向上一步
    now_step[0] -= 1
    if now_step[0] < 0:
        pass
    elif maps[now_step[0]][now_step[1]] == 1:
        pass
    elif next_step(last_step, now_step, maps):
        steps.append(now_step)
    # 方向二，向左一步
    now_step = copy.copy(last_step)
    now_step[1] -= 1
    if now_step[1] < 0:
        pass
    elif maps[now_step[0]][now_step[1]] == 1:
        pass
    elif next_step(last_step, now_step, maps):
        steps.append(now_step)
    # 方向三，向下一步
    now_step = copy.copy(last_step)
    now_step[0] += 1
    if now_step == [h, w]:
        steps.append(now_step)
        break
    if now_step[0] > h:
        pass
    elif maps[now_step[0]][now_step[1]] == 1:
        pass
    elif next_step(last_step, now_step, maps):
        steps.append(now_step)
    # 方向四，向右一步
    now_step = copy.copy(last_step)
    now_step[1] += 1
    if now_step == [h, w]:
        steps.append(now_step)
        break
    if now_step[1] > w:
        pass
    elif maps[now_step[0]][now_step[1]] == 1:
        pass
    elif next_step(last_step, now_step, maps):
        steps.append(now_step)
    last_step = copy.copy(steps[-1])
# 结果输出
for i in range(len(steps)):
    print('('+str(steps[i][0])+','+str(steps[i][1])+')')