AcWing 1076. 迷宫问题
原题链接
简单
作者:
沐枫w
,
2024-03-14 19:51:44
,
所有人可见
,
阅读 15
//参考了第一个题解的思路(逆向宽搜+正向打印),但代码都是自己写的
#include<bits/stdc++.h>
using namespace std;
int n;
bool a[1010][1010],fl[1010][1010];
typedef pair<int, int> PII;
PII pre[1010][1010];
int dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,1,-1 };
void bfs(int i, int j)
{
queue<PII> q;
q.push({ i,j });
fl[i][j] = 1;
while (q.size())
{
PII h = q.front();
q.pop();
for (int k = 0; k < 4; k++)
{
int x = h.first + dx[k];
int y = h.second + dy[k];
if (a[x][y] == 0 && x >= 1 && x <= n && y >= 1 && y <= n && fl[x][y] == 0)
{
fl[x][y] = 1;
q.push({ x,y });
pre[x][y] = h;
if (x == 1 && y == 1)
return;
}
}
}
}
int main() {
cin >> n;
for(int i=1;i<=n;i++)
for (int j = 1; j <= n; j++)
{
cin >> a[i][j];
}
bfs(n, n);
int xx=1, yy=1;
while (xx < n || yy < n)
{
int ll, rr;
cout << xx-1 <<" "<< yy-1<<endl;
ll = xx, rr = yy;
xx = pre[ll][rr].first;
yy = pre[ll][rr].second;//如果用xx = pre[xx][yy].first;yy = pre[xx][yy].second;
//计算xx时会改变xx导致yy的xx不再是原来的xx,所以要再开个ll,rr存
}
cout << n-1 << " " << n-1;
}