问题描述】下图给出了一个迷宫的平面图，其中标记为黑色的为障碍，标记为白色的为可以通行的区域。迷宫的入口为左上角的黄色方格，出口为右下角的黄色方格。在迷宫中，只能从一个方格走到相邻的上、下、左、右四个方向之一。 image.png 找到一条从起点到终点的迷宫路径，并将路径输出。如果从起点到终点没有路径，则输出NO PASS! 注：所有迷宫的起点为左上角，终点为右下角。 【输入形式】依次输入n行由0和1构成的字符串，每行字符串长度相同，输入空串结束，其中1表示围墙，0表示可行路径。 【输出形式】如果起点到终点有路，则依次输出由L、R、D、U组成的路径字符串；否则输出NO PASS!。 【样例输入】 0111111 0011101 1001101 0011001 1000111 1110000 【样例输出】 DRDDDRRDRRR

以下是一个基于广度优先搜索算法的迷宫路径解法。每次扩展一个新的状态时，都检查其是否为终点，如果是则沿着父状态指针回溯输出路径。如果最终无法到达终点，则输出 NO PASS。

from queue import Queue

n = 6 # 迷宫的行数
m = 7 # 迷宫的列数

maze = []
for i in range(n):
    line = input().strip()
    if line:
        maze.append([int(x) for x in line])

# 定义上下左右四个方向的偏移量
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
dirs = ['U', 'R', 'D', 'L']

# 定义状态类
class State:
    def __init__(self, x, y, p):
        self.x = x
        self.y = y
        self.p = p # 父状态指针

# 定义 BFS 算法
def bfs(start, end):
    q = Queue()
    q.put(start)

    while not q.empty():
        cur = q.get()
        if cur.x == end.x and cur.y == end.y:
            # 到达终点，输出路径
            path = []
            while cur.p:
                path.append(cur.p)
                cur = cur.p
            return ''.join(path[::-1])

        for i in range(4):
            nx, ny = cur.x + dx[i], cur.y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m or maze[nx][ny] == 1:
                continue
            maze[nx][ny] = 1 # 标记已访问过的位置
            q.put(State(nx, ny, cur))
    
    # 无法到达终点，返回 NO PASS
    return 'NO PASS'

start = State(0, 0, None)
end = State(n-1, m-1, None)
maze[0][0] = 1 # 标记起点为已访问过的位置
print(bfs(start, end))

对于输入样例，上述代码将输出 `DRDDDRRDRRR`。