AcWing 1076. 迷宫问题
给定一个 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<iostream>
#include<queue>
#include<cstring>#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];
int n;
PII pre[N][N]; int dx[4]={
0,1,0,-1},dy[4]={
1,0,-1,0};void bfs(int sx,int sy)
{
queue<PII> q;q.push({
sx,sy});memset(pre,-1,sizeof pre);pre[sx][sy]={
-2,n};while(q.size()){
auto t=q.front();q.pop();for(int i=0;i<4;i++){
int tx=t.x+dx[i];int ty=t.y+dy[i];if(tx<1||ty<1||tx>n||ty>n)continue;if(g[tx][ty])continue;if(pre[tx][ty].x==-1){
q.push({
tx,ty});pre[tx][ty]=t;if(tx==1&&ty==1)return;}}}
}
int main(void)
{
cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>g[i][j];bfs(n,n);PII end=pre[1][1];cout<<"0 0"<<endl;while(end.x!=-2){
cout<<end.x-1<<" "<<end.y-1<<endl;end=pre[end.x][end.y];}
}