bfs在矩阵迷宫中搜索路径时，若未标记已访问节点，会导致同一位置反复入队，引发队列持续增长、永不为空的死循环。关键在于引入访问标记机制，避免重复访问。
在您提供的代码中，BFS逻辑结构基本正确：从起点入队，逐层扩展上下左右四个方向的合法邻居，并通过 Box 节点的 parent 字段回溯路径。但核心缺陷在于缺少访问状态管理——程序未记录哪些坐标已被探索过，导致节点反复被重新加入队列。
例如，从 (0,0) 扩展到 (0,1) 后，当 (0,1) 出队时又会检查 (0,0)（左邻），而此时 (0,0) 仍满足 isFree() 条件（值为 0 且坐标合法），于是重新入队。如此往复，形成环路，队列无限膨胀。
✅ 正确做法是：每弹出一个节点（poll()）后，立即标记其坐标为“已访问”；后续所有邻居入队前，必须同时校验边界、可通行性 和 未访问状态。
推荐使用二维布尔数组 visited[][] 实现标记（也可复用原矩阵做原地标记，但需谨慎处理）：
public static void searchPath(int[][] maze, int startX, int startY, ArrayListpath) { int rows = maze.length; int cols = maze[0].length; boolean[][] visited = new boolean[rows][cols]; // 新增访问标记数组 Queue queue = new LinkedList<>(); // 避免静态变量，防止多线程/多次调用冲突 queue.add(new Box(startX, startY, null)); visited[startY][startX] = true; // 入队即标记 while (!queue.isEmpty()) { Box p = queue.poll(); if (maze[p.y][p.x] == 9) { System.out.println("Exit is reached!"); getPath(p, maze, path); return; } // 四方向扩展（顺序无关紧要） int[][] directions = {{1,0}, {-1,0}, {0,1}, {0,-1}}; for (int[] dir : directions) { int nx = p.x + dir[0]; int ny = p.y + dir[1]; if (isFree(maze, nx, ny) && !visited[ny][nx]) { visited[ny][nx] = true; // 入队前标记，防重复 queue.add(new Box(nx, ny, p)); } } } System.out.println("No path found."); } // isFree 保持不变，但注意：原实现中 maze[y][x] 的索引顺序需与实际矩阵维度一致（此处假设 maze[y][x] 正确） public static boolean isFree(int[][] maze, int x, int y) { if (x >= 0 && x < maze[0].length && y >= 0 && y < maze.length) { int val = maze[y][x]; return val == 0 || val == 2 || val == 9; // 仅允许通路、路径标记、终点 } return false; }
⚠️ 重要注意事项：
-
避免静态队列：原代码中 public static Queue
q 是危险设计。静态变量跨调用持久化，易引发状态污染；应改为局部变量或通过参数传递。 - 索引一致性：maze[y][x] 表示第 y 行、第 x 列，需确保 maze 是 rows × cols 结构（即 maze.length 为行数，maze[0].length 为列数）。isFree() 中 maze[y][x] 的行列顺序必须与矩阵实际布局严格匹配。
- 标记时机：务必在 queue.add() 之前 设置 visited[ny][nx] = true，否则在高并发或多分支场景下仍可能因竞态导致重复入队。
- 内存与性能：对大型迷宫，visited 数组是必要开销；若内存受限，可考虑将已访问位置在 maze 中临时设为 -1 等非法值（但需保证不影响 isFree() 判断逻辑）。
总结：BFS 的本质是层级遍历，其正确性依赖于每个节点仅被处理一次。缺失访问标记是初学者最常犯的错误之一。加上 visited 数组并规范标记时机，即可彻底解决死循环问题，确保算法在 O(M×N) 时间内稳定完成搜索。
