- 当要求
最短路径时，并且边的权值为1时 使用BFS(广度优先搜索。)
思路
- 用
g[n][m]存储地图，d[n][m]存储起点到 n,m 的距离。 - 从起点开始广度优先遍历地图。
- 当地图遍历完，就求出了起点到各个点的距离，输出
d[n][m]即可。
图讲解
使用队列的原因
- 因为当走到一个点后，有四种选择方向，必须同时向四个方向走，但是计算机一次性就只能执行一步，所以将待处理的方向依次放到队列中
- 每次走到相应点，就从队列中取出，看看是往哪个方向走
题目
方法1：模拟队列
#include <iostream>
#include<cstring>
#include<algorithm>
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)); //距离初始化为- 1表示没有走过
d[0][0] = 0; //表示起点走过了
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; //定义x方向的向量和y方向的向量
while (hh <= tt) //队列不为空
{
PII t = q[hh ++]; // 取出队头元素
for (int i = 0; i < 4; i ++) //枚举四个方向
{
int x = t.first + dx[i], y =t.second + dy[i]; ////x表示沿着此方向走会走到哪个点
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;
}
方法2：STL
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 110;
typedef pair<int, int> PII;
int n, m;
int g[N][N], d[N][N];
int bfs()
{
queue< pair<int, int> > q;
q.push({0, 0});
memset(d, -1, sizeof(d));
d[0][0] = 0;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
while (q.size())//队列不为空
{
PII t = q.front();//取队头元素
q.pop();//出队
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.push({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;
}
return d[n-1][m-1]是最小路径
- 第一次找到这个点的时候(即最短距离)这个点就被标记了 如果下次访问这个点就访问不到(所以不是找到了就跳出循环）
- 访问不到后，队列中的元素会为依次弹出，当队列为空时就退出循环。
打印路径
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 110;
typedef pair<int, int> PII;
PII q[N*N],Prev[N][N]; //多开个数组，记录一下前面一个点是多少
int g[N][N], d[N][N];
int n, m;
int bfs()
{
int hh = 0, tt = 0;
q[0] = {0, 0};
memset(d, -1, sizeof d);
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
d[0][0] = 0;
while(hh <= tt)
{
PII t = q[hh ++ ];
for(int i = 0; i < 4; i ++ )
{
int x = dx[i] + t.first, 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;
Prev[x][y] = t; //将前面一个点存储起来
q[++ tt] = {x, y};
}
}
}
int x = n - 1, y = m - 1;
while(x || y)//有一个不d等于0
{
cout << x << ' ' << y << endl; //打印目前点
PII t = Prev[x][y]; //寻找前面一个点，继续打印
x = t.first, y = t.second;
}
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;
}
