题目:样例:
|
|
思路:
这里刚开始看的时候会可能有点复杂了,因为是递归。
但是只要理解了含义,脑袋里模拟一下还是可以理解的。首先还是 之前那样 BFS 常规搜索
只是这里不用输出步数了,所以我们可以省略一层循环,直接搜索求路径。
求路径的方法核心思想就是 记录每个点是由哪上一个点所得来的。
然后记录完全部的点所对应的上一个点后,从终点递归一遍到起点,然后输出路径即可。文章来源:https://www.toymoban.com/news/detail-682473.html
代码详解如下:
#include <iostream>
#include <queue>
#include <cstring>
#define endl '\n'
#define x first
#define y second
#define mk make_pair
#pragma GCC optimize(3,"Ofast","inline")
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 300;
using PII = pair<int, int>;
// 控制走动方向
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int n, m; // 迷宫大小
int r[N][N]; // 记录走动过的地方
int g[N][N]; // 迷宫地图
PII pre[N][N]; // 记录路径
// 走动下一个坐标条件
inline bool isRun(int x, int y)
{
return (x >= 0 && x < n && y >= 0 && y < m && !r[x][y] && !g[x][y]);
}
inline bool BFS(int x, int y)
{
// 存储坐标
queue<PII>q;
// 存储起点
q.push(mk(x, y));
// 开始广度搜索
while (q.size())
{
auto now = q.front();
q.pop();
if (now.x == n - 1 && now.y == m - 1)
{
// 如果已经走动到了右下角的出口
// 结束搜索
return false;
}
// 标记已经走动过了当前的地点
r[now.x][now.y] = true;
// 枚举四个方向能否走动
for (int i = 0; i < 4; ++i)
{
// 取出该方向的坐标
int bx = now.x + dx[i];
int by = now.y + dy[i];
// 判断是否满足走动条件
if (isRun(bx, by))
{
// 存储下一次走动的坐标
q.push(mk(bx, by));
// 标记下一次会走动的坐标
r[bx][by] = true;
// 记录路径
// 下一个点是 由 哪上一个最优的点得到的
// 然后 反过来递归回去找 就得到 起点到终点的路径了
pre[bx][by] = mk(now.x, now.y);
}
}
}
// 如果不能走到终点输出结果
return true;
}
inline void Print_path(PII now)
{
// 取出当前 now 对应的上一个的坐标
auto previous = pre[now.x][now.y];
// 如果递归到达了边界,说明已经到达了起点
// 开始输出路径
if (previous == PII(-1, -1))
{
cout << now.x + 1 << ' ' << now.y + 1 << endl;
return ;
}
// 继续递归往回找路径
Print_path(previous);
cout << now.x + 1 << ' ' << now.y + 1 << endl;
return ;
}
inline void solve()
{
// 这里是初始化路径全部为 -1,-1,作为递归边界
memset(pre, -1, sizeof pre);
cin >> n >> m;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
cin >> g[i][j];
}
}
if (BFS(0, 0))
{
puts("-1");
}
else
{
// 打印路径
// 由于是从后面开始记录上一个路径点
// 所以我们应该从终点开始递归查找路径
Print_path(mk(n - 1, m - 1));
}
}
int main()
{
// freopen("a.txt", "r", stdin);
___G;
int _t = 1;
// cin >> _t;
while (_t--)
{
solve();
}
return 0;
}
最后提交:
文章来源地址https://www.toymoban.com/news/detail-682473.html
到了这里,关于BFS4专题 迷宫最短路径(输出路径)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!