AcWing 1076. 迷宫问题
原题链接
简单
作者:
mkuiwu
,
2021-02-10 16:11:18
,
所有人可见
,
阅读 212
#include<iostream>
#include<algorithm>
#include<cstring>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1010, M = N*N;
// 可以通过记录父亲节点来查找路径
PII path[N][N], q[M];
int g[N][N];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
// 2. 记录当前位置
int st[N][N];
int n;
void bfs(int sx, int sy){
memset(st, -1, sizeof st);
int hh = 0, tt = 0;
q[0] = {sx, sy};
st[sx][sy] = 1;
path[sx][sy] = {-1, -1};
while(hh <= tt){
auto t = q[hh ++];
for(int i = 0; i < 4 ; i++){
int a = t.x + dx[i], b = t.y + dy[i];
// 如果已经结束
if(t.x == t.y && t.x == 0)return;
// 合法性判断
if(a < 0 || a >= n || b < 0 || b >= n) continue;
if(st[a][b] != -1 || g[a][b] == 1) continue;
// 入队
q[++ tt] = {a, b};
// st 其实可以拿来记录步数
st[a][b] = 1;
// 加入路径, 直接等于是复制
path[a][b] = t;
}
}
}
int main(){
cin >> n;
for(int i = 0; i < n ; i++)
for(int j = 0; j < n; j++)
scanf("%d", &g[i][j]);
bfs(n-1, n-1);
// 然后要找到合适的值
cout << "0 0" << endl;
PII t = path[0][0];
while (1)
{
if(t.x == -1 && t.y == -1) break;
cout << t.x << ' ' << t.y << endl;
t = path[t.x][t.y];
}
return 0;
}