acwing1076. 迷宫问题

题目

给定一个 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表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

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

题解

需要用pair<int,int>pre[][]数组来记录上一步的坐标

#include<iostream>
#include<cstring>
#define x first
#define y second
using namespace std;
typedef pair<int,int>PII;
const int N=1010;
int g[N][N];
PII q[N*N];
PII pre[N][N];
int n;

void bfs(int i,int j){
    int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
    int hh=0,tt=0;
    q[0]={i,j};
    memset(pre,-1,sizeof pre);
    while(hh<=tt){
        PII t=q[hh++];
        for(int k=0;k<4;k++){
            int a=t.x+dx[k],b=t.y+dy[k];
            if(a<0||a>=n||b<0||b>=n)continue;
            if(g[a][b])continue;
            if(pre[a][b].x!=-1)continue;
            q[++tt]={a,b};
            pre[a][b]=t;
        }
    }
    
}
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 end(0,0);
    while(true){
        cout<<end.x<<" "<<end.y<<endl;
        if(end.x==n-1&&end.y==n-1)break;
        end=pre[end.x][end.y];
    }
    
    return 0;
}