HJ43 迷宫问题

本节目标：理解“HJ43 迷宫问题”的核心思路，并能把它用于实际开发或面试表达。 中等 通过率：33.18% 时间限制：1秒 空间限制：32M 知识点 ==查找== ==dfs== ==广度优先搜索(BFS)== 描述 定义一个二维数组 N*M ，如 5 × 5 数组下所示：

int maze[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, };

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路。 数据范围：2≤n,m≤10 ， 输入的内容只包含 0≤val≤1 输入描述： 输入两个整数，分别表示二维数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。 输出描述： 左上角到右下角的最短路径，格式如样例所示。 示例1 输入： 5 50 1 0 0 00 1 1 1 00 0 0 0 00 1 1 1 00 0 0 1 0 ==复制== 输出： (0,0)(1,0)(2,0)(2,1)(2,2)(2,3)(2,4)(3,4)(4,4) ==复制== 示例2 输入： 5 50 1 0 0 00 1 0 1 00 0 0 0 10 1 1 1 00 0 0 0 0 ==复制== 输出： (0,0)(1,0)(2,0)(3,0)(4,0)(4,1)(4,2)(4,3)(4,4) ==复制== 说明： 注意：不能斜着走！！

这段代码是为了找到一个从迷宫入口（左上角）到出口（右下角）的路径，它使用了一种叫做广度优先搜索（BFS）的方法。下面是每一行代码的解释，用小学生也能理解的方式：

注意：

• 走过的不再走
• 要有一个终止条件
• 四种情况的if用for循环四次来取代，因为逻辑是一样的
• 至于如何得到路径，因为每一次循环都POP一下，如果走不通的，最终不会保留

定义一个用来在迷宫中找路径的函数

def bfs(maze):

获取迷宫的行数和列数

m, n = len(maze), len(maze[0])

如果迷宫是空的，就没有路径

if m == 0 or n == 0: return []

准备一个队列，开始时只有起点在里面

queue = [(0, 0, [(0, 0)])]

记录我们访问过的地方，开始时只有起点

==visited== ===== ==set====([(====0====,== ==0====)])==

当队列不为空时，继续寻找路径

while queue:

从队列中取出一个位置和到这个位置的路径

row, col, path = queue.pop(0)

如果这个位置是出口，就找到了路径

if (row, col) == (m - 1, n - 1): return path

尝试向上下左右四个方向移动

==for== ==dx====,== ==dy== ==in== ==[(-====1====,== ==0====), (====1====,== ==0====), (====0====, -====1====), (====0====,== ==1====)]:==

计算移动后的位置

next_row, next_col = row + dx, col + dy

如果新位置有效，并且没有被墙挡住，并且没有访问过

if ( ==0== ==<=== ==next_row== ==<== ==m== ==and== ==0== ==<=== ==next_col== ==<== ==n== ==and== ==maze====[====next_row====][====next_col====] ==== ==0== ==and== ==(====next_row====,== ==next_col====)== ==not in== ==visited== ):

将新位置和到达新位置的路径加入队列

queue.append( (next_row, next_col, path + [(next_row, next_col)]))

标记新位置为已访问

visited.add((next_row, next_col))

如果走遍了所有可能的路都没有找到出口，就返回空列表

return []

不停地读取输入，直到没有更多数据

while True: try:

读取迷宫的行数和列数

m, n = map(int, input().split()) maze = []

根据行数读取迷宫数据

for _ in range(m): row = list(map(int, input().split())) maze.append(row)

使用BFS方法找路径

path = bfs(maze)

打印找到的路径

for step in path: print(f"({step[0]},{step[1]})")

如果读取数据时出错（例如没有更多数据了），就结束程序

except EOFError: break

在这个代码中，我们首先定义了一个名为 bfs 的函数来寻找迷宫的路径。它首先检查迷宫是否为空，然后使用一个队列来存储我们尝试过的路径。我们从起点开始，逐步尝试向上、下、左、右四个方向移动，直到找到出口或者走遍所有可能的路。在主循环中，我们读取迷宫的大小和布局，然后调用 bfs 函数来寻找路径，并把路径打印出来。