华为机考 迷宫问题 DFS python

发布于:2023-01-04 ⋅ 阅读:(180) ⋅ 点赞:(0)

注意边界上下左右,在起点时是不能往上和左走的
有个地方我暂时理解不了,有了解的大佬还请不吝赐教
我在判断边界的时候,如果这么写,编译总是报错超出索引

#如果往上走不了,能不能往下走,能走则写入坐标
    elif  maze[r+1][c] == 0 and r+1 < n:

一直找不到原因,按理来说and应该是并行判断,用if的时候没问题,用elif就出问题了
改成这样就没问题了

#如果往上走不了,能不能往下走,能走则写入坐标
    elif r+1 < n and maze[r+1][c] == 0 :
"""
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

"""
n,m = map(int,input().split())   #n行m列
maze =[]
for i in range(n):   #每行输入 存储迷宫
    maze.append(list(map(int,input().split())))


#坐标存储
coords = []
start = (0,0)
end = (n-1,m-1)    #边界/结束 ,设置起始点
coords = [start]
while coords:   #当坐标不为空时
    #当前节点
    now = coords[-1]   #最后一个坐标
    r,c = now          #解包,(1,2)-->r=1,c=2
    maze[r][c] = 2     #标记走过的坐标,用任意数将0覆盖,
    # 往上能不能走
    if now == end:
        for i in coords:
            print(f'({i[0]},{i[1]})')
        break
    if maze[r-1][c] == 0 and r!=0: #往上可以走(行不为0的时候),则写入坐标
        coords.append((r-1,c))
        continue
    #如果往上走不了,能不能往下走,能走则写入坐标
    elif r+1 < n and maze[r+1][c] == 0 :
        coords.append((r+1,c))
        continue
    #上下走不了,左边能不能走
    elif maze[r][c-1] == 0 and c!=0 :
        coords.append((r,c-1))
        continue
    #上下左都走不了,往右
    elif c+1 < m and maze[r][c+1] == 0 :
        coords.append((r,c+1))
        continue
    else:    #上下左右都不能走了(来时的路已经用其他数字覆盖0了),将最后一项去掉
        coords.pop()  #走到死胡同的时候,由于来路都被标记过了,所以会一直移除来时的坐标直到最近的岔路,然后走没走过的那一条
else:
    print("无路可走")

思路来源视频添加链接描述