11.迷宫问题

原题链接：https://www.acwing.com/problem/content/description/1078/

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;

#define x first
#define y second
typedef pair<int,int> PII;
const int N=1010;
int n,hh,tt;
int g[N][N],dist[N][N];
PII q[N*N],pre[N][N];
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};

void bfs()
{
    hh=0,tt=0;
    q[0]={0,0};
    memset(dist,-1,sizeof dist);
    dist[0][0]=0;
    while(hh<=tt)
    {
        PII t=q[hh++];
        if(t.x==n-1&&t.y==n-1) return;
        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(g[x][y]==1) continue;
            if(dist[x][y]==-1)
            {
                dist[x][y]=dist[t.x][t.y]+1;
                pre[x][y]={t.x,t.y};
                q[++tt]={x,y};
            }
        }
    }
}

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();
    int a=pre[n-1][n-1].x,b=pre[n-1][n-1].y;
    vector<PII> nums;
    nums.push_back({n-1,n-1});
    while(a||b){
        nums.push_back({a,b});
        int t1=pre[a][b].x,t2=pre[a][b].y;
        a=t1,b=t2;
    }
    nums.push_back({0,0});
    for(int i=nums.size()-1;i>=0;i--)
    {
        printf("%d %d\n",nums[i].x,nums[i].y);
    }
    return 0;
}