蓝桥 迷宫 Python dfs

"""
https://www.bilibili.com/video/BV16C4y1s7EF/?spm_id_from=333.788.videocard.0
"""
# 用0代表障碍物， 用1代表可行路      True代表已访问， False 代表未访问
from pprint import pprint

"""
起点 0 0
1 1 0 1
1 1 1 1
1 1 0 1
1 0 1 1
0 0 0 1
终点 3 2
"""
maze = [[1, 1, 0, 1],
        [1, 1, 1, 1],
        [1, 1, 0, 1],
        [1, 0, 1, 1],
        [1, 1, 1, 1]]
x_end = 3
y_end = 2
MIN_STEP = float('inf')
# x + dx[0], y + dy[0] 表示向右走
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

dic_path = ['R', 'D', 'L', 'U']
v = [[False for _ in range(len(maze[0]))] for _ in range(len(maze))]
v[0][0] = True
PATH = ''
MIN_PATH = None


def dfs(x, y, step):
    global x_end, y_end, dx, dy, maze, MIN_STEP, PATH, MIN_PATH
    if x == x_end and y == y_end:
        if MIN_STEP > step:
            MIN_STEP = step  # 更新最小步数
            MIN_PATH = PATH  # 更新路径
        return
    for i in range(4):
        try:  # 运用try使得：当if不成立时，tx保持当前位置
            tx = x + dx[i]
            ty = y + dy[i]
            if maze[tx][ty] == 1 and v[tx][ty] == False:
                v[tx][ty] = True		# 记录该点
                PATH += dic_path[i]
                dfs(tx, ty, step + 1)  #搜索下一个点
                v[tx][ty] = False
                PATH = PATH[:-1]
        except:
            continue
    return MIN_STEP, MIN_PATH


print(dfs(0, 0, 0))