BFS记路径

我们可以开一个数组去记一下当前的点是由哪个点走过来的，然后设置一个起点，倒着输出就可以

如果题目让我们正着走的话，其实我们可以倒着走，然后正着输出。（下面给出一道例题）。

例题：1076. 迷宫问题

题意：给你一个n*n的矩阵，然后二维矩阵由0和1组成，我们只能走0不能走1然后问我们从头走到尾部的最短路径（题目保证一定有解）。

解题思路：我们可以通过BFS倒着搜一遍，然后正着输出，，具体的记路径的话，就是我们可以开一个pre数组去记一下我们现在这个点是由哪一个点出过来的

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int dx[5] = {0,-1,1,0,0};
int dy[5] = {0,0,0,-1,1};
const int N = 1e3 + 10;
int g[N][N];
bool st[N][N];
queue<pair<int,int>> q;
pair<int,int> pre[N][N];    //开一个数组去记路径
int n;

void bfs(int x,int y)
{
	int nowx,nowy,nex,ney;
	q.push({x,y});
	st[x][y]=true;
	while(q.size())
	{
		nowx = q.front().first,nowy = q.front().second;
		q.pop();
		for(int i=1;i<=4;i++)
		{
			nex=nowx+dx[i],ney=nowy+dy[i];
			if(nex>=0&&nex<n&&ney>=0&&ney<n&&st[nex][ney]==false&&g[nex][ney]==0)
			{
				st[nex][ney]=true;
				q.push({nex,ney});
				pre[nex][ney]={nowx,nowy};//记一下当前这个点是由哪个点走过来的
			}
		}
	}
}

int main()
{
	scanf("%d",&n);
	
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			scanf("%d",&g[i][j]);
	
	bfs(n-1,n-1);    //倒着搜一遍，然后我们直接正着输出就行
	
	
	pair<int,int> end(0,0);    //设置一下起点
	while(true)
	{
		printf("%d %d\n",end.first,end.second);
		if(end.first == n - 1 && end.second == n - 1) break;
		end = pre[end.first][end.second];
	}
	
	return 0;
}