使用 BFS 解决走迷宫问题

青旅半醒 2024-02-20 08:48 50阅读 0赞

## **使用 BFS 解决走迷宫问题** ##

**题目背景**:

在一个由 0 和 1 构成的二维迷宫中，0 代表可以走的路径，而 1 代表墙或障碍物。任务是从迷宫的左上角出发，找到到达右下角的最短路径。这是计算机科学中的经典问题，对于理解图搜索和路径查找算法具有重要意义。

**为何使用 BFS 和队列**:

广度优先搜索（BFS）是一个层次化的搜索过程，首先访问起始节点，然后访问所有相邻的节点，再访问这些节点的邻居，以此类推。这种方法确保我们在探索更远的节点之前，首先探索所有近邻节点。

使用队列是实现 BFS 的关键。因为 BFS 要求我们首先访问早先加入的节点（先进先出），而队列具有这样的特性。我们从起点开始，将其加入队列，然后持续处理队列中的元素，每次从队头取出一个节点，访问它的邻居，并将未访问的邻居加入队尾。

**解题思路及代码**:

#include<bits/stdc++.h>
    using namespace std;
    typedef pair<int, int> PII;
    const int N = 110;
    int n, m;
    int g[N][N];
    int d[N][N];
    PII q[N * N];
    
    int bfs()
    {
        
        int hh = 0, tt = 0;
        q[0] = {
        0, 0};
        memset(d, -1, sizeof(d));
        
        d[0][0] = 0;
        int dx[4] = {
        -1, 0, 1, 0};
        int dy[4] = {
        0, 1, 0, -1};
        while(hh <= tt)
        {
        
            auto t = q[hh ++];
            for (int i = 0; i < 4; ++ i)
            {
        
                int x = t.first + dx[i], y = t.second + dy[i];
                if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1)
                {
        
                    d[x][y] = d[t.first][t.second] + 1;
                    q[++ tt] = {
        x, y};
                }
            }
        }
        return d[n - 1][m - 1];
    }
    
    int main()
    {
        
        cin >> n >> m;
        for (int i = 0; i < n; ++ i)
        {
        
            for (int j = 0; j < m; ++ j) cin >> g[i][j];
        }
        cout << bfs() << endl;
        return 0;
    }

**代码解释**:

*  我们使用二维数组 `g[][]` 来存储迷宫信息。
 *  `d[][]` 存储从起点到每个点的最短距离。
 *  `q[]` 是用来进行 BFS 的队列，每个元素表示迷宫中的一个点。
 *  `dx[]` 和 `dy[]` 是方向数组，帮助我们方便地探索当前点的四个方向。
 *  `bfs()` 函数中，我们从起点开始，然后逐渐探索每一层直到到达终点或者探索完所有可能的路径。