1ji0o's Blog

迷宫寻址(dfs bfs)

6分钟阅读

答案是肯定的。

在网格（Grid）地图里找迷宫路径，绝对是深搜（DFS）和广搜（BFS）的最经典应用场景。

在 2 小时的上机考试中，你应该如何选择？我给你一个最功利的判断标准：

  1. 如果题目只要求“找到一条路径”（或者说“能不能到达终点”）：无脑用 DFS。
    • 原因：代码短，逻辑简单（递归），不需要维护队列，写起来最快。
  2. 如果题目明确要求“找到最短路径”：必须用 BFS。
    • 原因：DFS 找出来的路通常是绕弯的，只有 BFS 层层外扩的特性才能保证找到的是最短的。

鉴于考试时间紧，且往年题目（如 2023 小雪人）通常只要求“找到任意一条符合条件的路径”，我强烈建议你熟练掌握 DFS 的写法。

一、 迷宫 DFS 算法模板（背下来）

这是一个通用的网格 DFS 模板。 假设 map[x][y] == 0 是路，1 是墙。

数据结构准备： 在 MainWindow 类中：

std::vector<QPoint> path; // 记录路径，用于最后画图
bool visited[20][20];     // 访问标记，防止死循环 (假设最大20x20)
// 或者用 vector<vector<bool>> visited;

核心代码：

// 返回值 bool: true表示找到路了，false表示没找到
bool MainWindow::dfs(int x, int y) {
    // 1. 【越界检查】 & 【障碍检查】 & 【已访问检查】
    if (x < 0 || x >= M || y < 0 || y >= N) return false; // 越界
    if (map[x][y] == 1) return false;                     // 撞墙
    if (visited[x][y]) return false;                      // 走回头路
 
    // 2. 【记录当前点】
    path.push_back(QPoint(x, y)); // 加入路径
    visited[x][y] = true;         // 标记已走过
 
    // 3. 【终点判断】
    if (x == endX && y == endY) {
        return true; // 到达终点，大功告成，一路返回 true
    }
 
    // 4. 【递归试探】 (上下左右)
    // 方向数组: 下, 右, 上, 左
    int dx[] = {1, 0, -1, 0};
    int dy[] = {0, 1, 0, -1};
 
    for (int i = 0; i < 4; ++i) {
        int nextX = x + dx[i];
        int nextY = y + dy[i];
        
        // 关键点：如果深层递归返回 true，说明找到路了，我也返回 true
        if (dfs(nextX, nextY)) {
            return true; 
        }
    }
 
    // 5. 【回溯 (Backtracking)】
    // 如果四个方向都走不通，说明 (x,y) 是死胡同
    path.pop_back(); // 把它从路径里踢出去
    
    // 注意：如果是找"一条"路径，通常不需要 visited[x][y] = false;
    // 这样能保留"死胡同"标记，防止以后再进来，效率更高。
    
    return false; 
}

二、 如何把路径“画”出来？

题目提到的“把路径画出来”通常有两种画法，你要看题目截图：

画法 1：格子填色（最常见）

就是我们之前练习的，把路径上的格子涂成蓝色/黄色。

实现思路：

  1. 执行 dfs(startX, startY) 成功后，path 向量里存的就是正确的坐标序列。
  2. 在 paintEvent 里，先画地图背景。
  3. 再遍历 path 数组，把对应的格子重画一遍颜色。
void MainWindow::paintEvent(QPaintEvent *) {
    QPainter painter(this);
    // ... 画网格背景 ...
 
    // 画路径
    painter.setBrush(Qt::blue); // 设置路径颜色
    for (const auto& p : path) {
        // 转换坐标: 行=p.x(), 列=p.y() (假设你DFS里x是行)
        // 记得你的像素转换公式: margin + index * size
        double px = leftMargin + p.y() * cellW; 
        double py = topMargin + p.x() * cellH;
        painter.drawRect(QRectF(px, py, cellW, cellH));
    }
}

画法 2：画线条连接（Polyline）

如果题目要求像手机锁屏图案那样，用线条把中心点连起来。

实现思路：

  1. DFS 跑完拿到 path。
  2. 在 paintEvent 里使用 painter.drawLine。
void MainWindow::paintEvent(QPaintEvent *) {
    // ... 
    painter.setPen(QPen(Qt::red, 3)); // 红色线条，线宽3
 
    for (size_t i = 0; i < path.size() - 1; ++i) {
        QPoint p1 = path[i];
        QPoint p2 = path[i+1];
 
        // 算出两个格子的【中心点】像素坐标
        // CenterX = Margin + Col * W + W/2
        double x1 = leftMargin + p1.y() * cellW + cellW/2;
        double y1 = topMargin + p1.x() * cellH + cellH/2;
 
        double x2 = leftMargin + p2.y() * cellW + cellW/2;
        double y2 = topMargin + p2.x() * cellH + cellH/2;
 
        painter.drawLine(QPointF(x1, y1), QPointF(x2, y2));
    }
}

总结

  • 找迷宫路径 = DFS（除非特别要求最短路径）。
  • 它的核心是：标记 visited → 递归邻居 → 回溯 pop。
  • 把这个模板背熟，考试时只需要改一下 if (map[x][y] == 1) 这种判断墙的条件即可。

关系图谱