AcWing 1076. 迷宫问题
原题链接
简单
作者:
papapiu
,
2021-09-03 17:32:33
,
所有人可见
,
阅读 214
#include <iostream>
#include <cstring>
#include <algorithm>
#define x first
#define y second
using namespace std;
const int N = 1010,M= N*N;
bool st[N][N];
int g[N][N],dist[N][N],n,m;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
typedef pair<int, int> PII;
PII pre[N][N];
void bfs(int sx,int sy){
int hh=0,tt=0;
dist[sx][sy] = 0;
PII q[M];
pre[sx][sy] = {0,0};
q[0] = {sx,sy};
st[sx][sy] = true;
while(hh<=tt){
auto t = q[hh++];
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(st[x][y]||g[x][y]==1) continue;
dist[x][y] = dist[t.x][t.y]+1;
st[x][y] = true;
pre[x][y] = t;
q[++tt] = {x,y};
}
}
}
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)
{
printf("%d %d\n", end.x, end.y);
if (end.x == n - 1 && end.y == n - 1) break;
end = pre[end.x][end.y];
}
return 0;
}
码风赞!!