经典迷宫问题广度优先搜索完美题解

大家好，我是 lz，今天来分享一下这道迷宫题目的题解。其实，这道题主要考察大家的搜索能力，而最合适的算法之一就是广度优先搜索（BFS）。

题目理解

题目要求我们判断这个迷宫是否可以从左上角 (0,0) 走到右下角 (n-1, m-1)。虽然 BFS 常常用于求解最短路径或最少步数，但它的遍历特性同样适用于这道判断路径是否存在的题目。BFS 可以帮助我们按层次（步数）逐步展开搜索，因此非常适合网格类迷宫问题。

解题思路

1.	准备工作：我们首先创建一个用于表示位置的结构体 Node，它包含当前格子的行和列信息。在 BFS 过程中，Node 结构体能帮助我们更清晰地存储并传递每个格子的坐标。
2.	初始化队列：我们用队列 queue<Node> q 来进行 BFS。这个队列会帮助我们按层次逐步搜索迷宫中的路径。每次从队列中取出一个节点时，就表示从起点到这个节点的路径是“可行”的。我们把起点 (0,0) 入队，并将其标记为“访问过”。
3.	BFS 主循环：接下来进入 BFS 主循环，每次取出队头节点，并检查该节点的所有可能的下一步位置（上下左右四个方向）。
•	如果我们发现某个节点刚好位于右下角 (n-1, m-1)，说明路径是通的，我们可以直接返回 true。
•	否则，我们尝试对四个方向的每一个相邻格子进行检查。如果这个相邻格子在迷宫范围内、是空地 0，并且没有被访问过，那么我们就将该格子入队并标记为“访问过”。
4.	结束条件：如果队列在 BFS 过程中被清空了，仍然没有找到通往右下角的路径，那说明这个迷宫没有解，我们返回 false。

最后给大家呈现我的代码题解，希望大家看了能有帮助，如果可以请记得关注我哦！感谢支持！
代码实现

这道题目的 BFS 实现其实是非常清晰的，只需几步就可以实现路径判断。具体代码如下：

#include <cstdio>
#include <queue>
using namespace std;

const int arr_size = 50;
int n, m;
int img[arr_size][arr_size];
bool vis[arr_size][arr_size];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

struct Node 
{
    int line, col;
};

bool bfs()
{
    queue<Node> q;
    q.push(Node{0, 0});
    vis[0][0] = true;
    while (!q.empty())
    {
        int lin = q.front().line;
        int col = q.front().col;
        q.pop();
        if (lin == n - 1 && col == m - 1) return true;
        for (int i = 0; i < 4; i++)
        {
            int new_lin = lin + dx[i];
            int new_col = col + dy[i];
            if (new_lin >= 0 && new_lin < n && new_col >= 0 && new_col < m &&
                !vis[new_lin][new_col] && img[new_lin][new_col] == 0)
            {
                q.push(Node{new_lin, new_col});
                vis[new_lin][new_col] = true;
            }
        }
    }
    return false;
}

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            scanf("%1d", &img[i][j]);
        }
    }
    if (bfs())
    {
        printf("YES\n");
    }
    else printf("NO\n");
    return 0;
}

重点解析

•	队列入队和出队：每次从队列中取出当前格子并检查四周可行的下一步。将可走的格子入队以便继续搜索。
•	避免重复访问：在每次入队之前，我们都将该格子标记为访问过，防止后续重复搜索。
•	终点判断：当我们找到右下角的格子时即可返回 true，不必再继续遍历。

适用的场景和优势

BFS 非常适合用于这类迷宫通路问题，尤其当迷宫的规模较小时（如本题最大 40x40）。它的层次遍历能帮助我们高效地找到路径。相比深度优先搜索（DFS），BFS 遇到目标会立即返回，不会走入无效路径。

希望这个题解能够帮助大家理解 BFS 在迷宫问题中的应用，关注我了解更多算法题解！谢谢！