AcWing 844. 走迷宫(bfs)
原题链接
简单
作者:
腾杨天下
,
2021-04-07 23:12:36
,
所有人可见
,
阅读 317
#include<bits/stdc++.h>
using namespace std;
typedef pair<int ,int> PII;
const int N=110;
int a[N][N],dis[N][N];
int n,m;
int bfs(PII start)
{
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
queue<PII> q;
q.push(start);
while(!q.empty())
{
PII u=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int x=u.first+dx[i];
int y=u.second+dy[i];
if(a[x][y]==1)continue;
if(x>0&&x<=n&&y>0&&y<=m&&a[x][y]==0&&dis[x][y]==-1)//如果这个点的dis值没有被更新过
//证明没有被搜过
//也就是说我们可以走到这个点
{
dis[x][y]=dis[u.first][u.second]+1;//一定要在新元素加入队列的时候就把新元素设为已到达
//我们更新祂的dis值自然就代表我们到达过这个点了
q.push({x,y});
}
}
}
return dis[n][m];
}
int main()
{
memset(dis,-1,sizeof dis);
dis[1][1]=0;//任何元素在加入队列之前都要标记成已到达,不可再拓展到,不然的话会tle,队头元素也不例外
//当然我们这道题,走到一个合法点的时候自然就会更新dis值了,既然dis值被更新了,那么我们就可以以
//dis值是否被更新过作为标准来判断这个点是否到达过了,这可以帮我们判断一个点是否是合法点
//(未到达过是其中的一个必要条件)
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)cin>>a[i][j];
}
cout<<bfs({1,1});
return 0;
}