当前位置：首页 > 文章列表 > 文章 > java教程 > 二维迷宫BFS路径查找算法详解

二维迷宫BFS路径查找算法详解

2026-01-10 18:39:44 0浏览收藏

今天golang学习网给大家带来了《二维迷宫BFS路径查找实现方法》，其中涉及到的知识点包括等等，无论你是小白还是老手，都适合看一看哦~有好的建议也欢迎大家在评论留言，若是看完有所收获，也希望大家能多多点赞支持呀！一起加油学习~

如何正确实现二维迷宫中的广度优先搜索（BFS）路径查找

本文详解 BFS 在 0/1/9 迷宫中查找目标值 9 失败的典型原因，重点指出坐标字符串哈希键未加分隔符导致哈希冲突的问题，并提供健壮、可复用的 BFS 实现方案。

在二维迷宫中使用 BFS 查找目标（如数字 9）是算法入门的经典场景，但一个看似微小的实现细节——坐标哈希键构造方式——往往导致搜索提前终止、路径遗漏甚至无限循环。上述代码的核心缺陷在于：

String ps = Integer.toString(p.x) + Integer.toString(p.y);

该写法将坐标 (1, 10) 和 (11, 0) 均映射为字符串 "110"，造成哈希冲突：一旦 (1, 10) 被标记为已访问，(11, 0) 将被错误跳过，即使它通向目标。这是典型的「无分隔符坐标拼接」陷阱。

✅ 正确做法是引入唯一、可解析的分隔符，例如冒号 :：

String key = p.x + ":" + p.y; // 推荐：简洁、语义清晰、无歧义
// 或更安全的格式化写法（防负数或大数干扰，但本题坐标非负，可选）
// String key = String.format("%d,%d", p.x, p.y);

此外，原代码存在多个可优化与修正点：

✅ 推荐重构要点

用 Set 替代 Map
HashMap 本质是模拟集合，徒增冗余。直接使用 Set（或自定义不可变坐标类）更语义准确、类型安全：

// 定义轻量坐标类（需重写 equals & hashCode！）
static class Pos {
    final int x, y;
    Pos(int x, int y) { this.x = x; this.y = y; }
    @Override public boolean equals(Object o) {
        if (!(o instanceof Pos)) return false;
        Pos p = (Pos) o;
        return x == p.x && y == p.y;
    }
    @Override public int hashCode() { return Objects.hash(x, y); }
}

// 使用 Set 管理已访问节点
Set<Pos> visited = new HashSet<>();

避免静态变量污染状态
原代码中 q 和 map_seen 为 public static，导致多次调用相互干扰、线程不安全。应改为局部变量或封装为实例方法：

public static List<int[]> searchPath(int[][] maze, int startX, int startY) {
    if (maze == null || maze.length == 0 || maze[0].length == 0) 
        return Collections.emptyList();

    Queue<Pos> queue = new LinkedList<>();
    Set<Pos> visited = new HashSet<>();
    Map<Pos, Pos> parent = new HashMap<>(); // 用于回溯路径

    Pos start = new Pos(startX, startY);
    queue.offer(start);
    visited.add(start);

    int[][] dirs = {{1,0}, {-1,0}, {0,1}, {0,-1}}; // 右、左、下、上

    while (!queue.isEmpty()) {
        Pos cur = queue.poll();

        // 检查是否到达目标
        if (cur.y >= 0 && cur.y < maze.length && 
            cur.x >= 0 && cur.x < maze[0].length &&
            maze[cur.y][cur.x] == 9) {

            return reconstructPath(parent, start, cur);
        }

        // 四方向扩展
        for (int[] d : dirs) {
            int nx = cur.x + d[0], ny = cur.y + d[1];
            Pos next = new Pos(nx, ny);

            if (isFree(maze, nx, ny) && !visited.contains(next)) {
                visited.add(next);
                parent.put(next, cur);
                queue.offer(next);
            }
        }
    }
    return Collections.emptyList(); // 未找到
}

isFree() 的健壮性增强
原方法在检查 maze[y][x] 前已确保边界有效，但建议将边界判断与值判断分离，提升可读性与调试友好性：

static boolean isFree(int[][] maze, int x, int y) {
    if (x < 0 || x >= maze[0].length || y < 0 || y >= maze.length) 
        return false;
    return maze[y][x] == 0 || maze[y][x] == 9;
}

路径重建示例
利用 parent 映射反向构建路径（从目标到起点），再反转输出：

static List<int[]> reconstructPath(Map<Pos, Pos> parent, Pos start, Pos target) {
    List<int[]> path = new ArrayList<>();
    for (Pos p = target; p != null; p = parent.get(p)) {
        path.add(new int[]{p.x, p.y});
    }
    Collections.reverse(path);
    return path;
}