我们在进行bfs的时候会将所有可能到达的点遍历并入队,但是我们只想要到达终点的那一条路径
易知到达终点的路径只有一条,但是我们每次存的是当前点是由那个点转移过来的,如果正着搜
不能输出从开始到结尾的路径,而且输出的路径也不一定对(到达终点的路径才是唯一的,从起点走的不一定唯一)
所以要倒着搜。
综上所述,倒着搜的原因一共有两点:
1、方便我们正着输出路径
2、从起点开始遍历的路径唯一
#include <iostream>
#include <cstring>
#include <algorithm>
#include<queue>
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 1010;
int g[N][N];
bool st[N][N];
PII pre[N][N];
int n;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
void bfs(int sx,int sy)
{
queue<PII>q;
q.push({sx,sy});
st[sx][sy] = true;
while(!q.empty())
{
PII t = q.front();
q.pop();
for(int i = 0; i < 4; i ++)
{
int x = t.x + dx[i],y = t.y + dy[i];
if(x < 0 || x >= n || y < 0 || y >= n)continue;
if(st[x][y])continue;
if(g[x][y] == 1)continue;
pre[x][y] = {t.x,t.y};
q.push({x,y});
st[x][y] = true;
}
}
}
int main()
{
cin >> n;
for(int i = 0; i < n; i ++)
for(int j = 0; j < n; j ++)
cin >> g[i][j];
bfs(n - 1,n - 1);
PII ed = {0,0};
while(1)
{
printf("%d %d\n",ed.x,ed.y);
if(ed == make_pair(n - 1,n - 1))break;
ed = pre[ed.x][ed.y];
}
return 0;
}