11.迷宫问题(BFS 储存路径)

迷宫问题

↑ 题目链接

题目

给定一个 \(n×n\) 的二维数组，如下所示：

int maze[5][5] = {

0, 1, 0, 0, 0,

0, 1, 0, 1, 0,

0, 0, 0, 0, 0,

0, 1, 1, 1, 0,

0, 0, 0, 1, 0,

};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

数据保证至少存在一条从左上角走到右下角的路径。

输入格式

第一行包含整数 \(n\)。接下来 \(n\) 行，每行包含 \(n\) 个整数 \(0\) 或 \(1\)，表示迷宫。

输出格式

输出从左上角到右下角的最短路线，如果答案不唯一，输出任意一条路径均可。
按顺序，每行输出一个路径中经过的单元格的坐标，左上角坐标为 \((0,0)\) ，右下角坐标为 \((n−1,n−1)\)

数据范围

$ 0≤n≤1000$

输入样例：

5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

输出样例：

0 0
1 0
2 0
2 1
2 2
2 3
2 4
3 4
4 4

思路

从终点往起点 \(BFS\) 搜索，第一次到达时保存路径，最后输出

代码

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int>PII;
const int N=1010;
int g[N][N];
bool st[N][N];
PII pre[N][N];
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
int n;

void bfs()
{
	queue<PII>q;
	q.push({n-1,n-1});
	st[n-1][n-1]=true;
	while(q.size())
	{
		auto t=q.front();
		q.pop();
		
		for(int i=0;i<4;i++)
		{
			int a=t.x+dx[i],b=t.y+dy[i];
			if(a<0||a>=n||b<0||b>=n||st[a][b]||g[a][b]==1)continue;
			pre[a][b]={t.x,t.y};//保存路径
			
			st[a][b]=true;
			q.push({a,b});
		}
	}
}

int main()
{
	cin>>n;
	
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			cin>>g[i][j];
	
	
	bfs();
	
	int x=0,y=0;
	
	while(1)
	{
	    cout<<x<<' '<<y<<endl;
	    if(x==n-1&&y==n-1)break;
	    int nowx=x,nowy=y;
		x=pre[nowx][nowy].x,y=pre[nowx][nowy].y;
	}
	
	
	return 0;
}