AcWing 1076. 迷宫问题(bfs进队列前判重 防止重复进入队列)
原题链接
简单
作者:
仅存老实人
,
2020-09-22 12:17:49
,
所有人可见
,
阅读 467
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=1010;
typedef pair<int,int> PII;
int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int g[N][N];
bool st[N][N];
int m,n;
PII pre[N][N];
void bfs()
{
queue<PII> q;
q.push({m-1,n-1});
memset(pre,-1,sizeof pre);
while(q.size())
{
auto t = q.front();
q.pop();//漏掉pop MLE了
int x = t.first,y=t.second;
if(x == 0 && y==0)
break;
for(int i=0;i<4;i++)
{// || pre[nx][ny].first!=-1
int nx=x+dirs[i][0],ny=y+dirs[i][1];
if(nx<0 || nx>=m || ny<0 || ny>=n || st[nx][ny] || g[nx][ny]==1) continue;
// 如果在进队列后st[x][y]==true
// 的时候不判断nx ny是否已经有pre 则可能出现重复进入队列 pre[nx][ny].first!=-1
q.push({nx,ny});
pre[nx][ny] = {x,y};
st[nx][ny] = true;//如果在进队列前st[nx][ny] = true; 就不会出现重复进入队列
}
}
int px = 0,py=0;
pre[m-1][n-1] = {-1,-1};
while(!(px==-1 && py==-1))//
{
cout << px << ' ' << py << endl;//不能写int px
auto t = pre[px][py];
px = t.first,py =t.second;
}
}
int main()
{
// int m,n; 在main中多定义了一次 导致bfs函数中m,n==0
cin >> m;
n=m;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
cin >> g[i][j];
}
}
bfs();
return 0;
}