返回题解分享
讨论 / 题解分享/ 帖子详情

走迷宫输出路径 - 题解

n, m = map(int, input().split())
a = [[0] * (m + 2)]
a += [[0] + list(map(int, input().split())) + [0] for _ in range(n)]
a += [[0] * (m + 2)]
startx, starty = map(int, input().split())
endx, endy = map(int, input().split())

dirs = [(0, -1), (-1, 0), (0, 1), (1, 0)]
paths = []

def dfs(x, y, path):
    if (x, y) == (endx, endy):
        paths.append(path[:])
        return
    a[x][y] = 0
    for dx, dy in dirs:
        nx, ny = x + dx, y + dy
        if a[nx][ny] == 1:
            path.append((nx, ny))
            dfs(nx, ny, path)
            path.pop()
    a[x][y] = 1

dfs(startx, starty, [(startx, starty)])

if paths:
    for path in paths:
        print("->".join(f"({x},{y})" for x, y in path))
else:
    print(-1)
0 回复 0 转发 0 喜欢 15 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!