目录
题目描述
题目描述：
给定一个二维迷宫，其中 0 表示可以走的路，1 表示障碍物。起点坐标为 (0, 0)，终点坐标为 (m-1, n-1)，其中 m 和 n 分别是迷宫的行数和列数。你需要使用广度优先搜索（BFS）找到从起点到终点的一条路径（如果存在的话），并输出该路径的长度。
输入格式：
第一行包含两个整数 m 和 n。
接下来 m 行，每行包含 n 个整数，表示迷宫的布局。
输出格式：
输出从起点到终点路径的长度，如果不存在这样的路径，则输出 -1。
样例输入：
5 6
0 1 0 0 0 0
0 1 0 1 1 0
0 0 0 0 1 0
0 1 1 1 0 0
0 0 0 1 0 0
样例输出：
13
思路
1.初始化：创建一个队列 q 用于存储待探索的坐标，创建一个二维数组 visited 用于记录每个坐标是否已被访问过，创建方向数组 dirs 用于表示上下左右四个方向。
2.起点入队：将起点坐标 (0, 0) 加入队列 q，并标记为已访问。
3.广度优先搜索：当队列不为空时，进行循环。每次循环中，先获取当前队列的大小，然后对当前队列中的所有坐标进行处理。对于每个坐标，首先判断是否是终点，如果是则返回当前步数。如果不是终点，则向四个方向探索，将符合条件的坐标加入队列并标记为已访问。
4.步数更新：每完成一轮循环，表示所有当前步数能到达的点都已探索完毕，步数加一。
5.结束：如果队列为空，表示无法到达终点，返回 -1。
AC 解答
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int bfs(vector<vector<int>>& maze, int m, int n) {
vector<vector<bool>> visited(m, vector<bool>(n, false));
queue<pair<int, int>> q;
vector<pair<int, int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
q.push({0, 0});
visited = true;
int steps = 0;
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; ++i) {
auto [x, y] = q.front();
q.pop();
if (x == m - 1 && y == n - 1) {
return steps;
}
for (auto& dir : dirs) {
int nx = x + dir.first;
int ny = y + dir.second;
if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny] && maze[nx][ny] == 0) {
q.push({nx, ny});
visited[nx][ny] = true;
}
}
}
++steps;
}
return -1;
}
int main() {
int m, n;
cin >> m >> n;
vector<vector<int>> maze(m, vector<int>(n));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
cin >> maze[i][j];
}
}
cout << bfs(maze, m, n) << endl;
return 0;
}