BFS 保存路径模板

因为BFS 相当于在一棵树上进行层次遍历。那么我们可以在每一个节点处记录下其父节点的坐标。然后从终点位置，回溯输出即可。

代码：

#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<string> #include<queue> #include<map> #include<stack> #include<set> //#include<unordered_map> #include<ctime> using namespace std; typedef long long ll; #define mst(ss,b) memset(ss,b,sizeof(ss)); #define rep(i,k,n) for(int i=k;i<=n;i++) #define INF 0x3f3f3f3f const ll maxn = 2e5 + 10;int dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,1,-1 }; int n = 5; int a[10][10]; struct node {int x, y; };node list[1010][1010]; //保存路径void bfs() {queue<pair<int, int>>q;q.push(pair<int,int>(0, 0));while (!q.empty()){int x = q.front().first, y = q.front().second;if (x == 4 && y == 4)return;q.pop();for (int i = 0; i <n ; ++i){int x1 = x + dx[i], y1 = y + dy[i];if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < n && a[x1][y1] == 0){a[x1][y1] = 1; //使用过置为 1 不能走（也可以开一个bool数组）list[x1][y1] = node{ x,y }; //保存上一个坐标 q.push(pair<int, int>(x1, y1));}}}return; }void show(int x, int y)//递归从叶子向根节点进行输出 {if (x == 0 && y == 0) {cout << "(" << x << ", " << y << ")" << endl;return;}show(list[x][y].x, list[x][y].y);cout << "(" << x << ", " << y << ")" << endl; }int main() {for (int i = 0; i < n; ++i)for (int j = 0; j < n; ++j)cin >> a[i][j];bfs();show(4,4);return 0; }

总结

以上是生活随笔为你收集整理的BFS 保存路径模板的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。