AcWing 844. 走迷宫-C++
原题链接
简单
作者:
码
,
2020-06-24 08:15:46
,
所有人可见
,
阅读 1570
#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=110;
int n,m;
int f[N][N],d[N][N];
int bfs()
{
queue<pair<int,int>> q;
q.push({1,1});
d[1][1]=0;
while(q.size())
{
int x[4]={-1,0,1,0},y[4]={0,1,0,-1};
auto t=q.front();
q.pop();
for(int i=1;i<=4;i++)
{
int X=t.first+x[i-1],Y=t.second+y[i-1];
if(X>=1 && X<=n && Y>=1 && Y<=m && d[X][Y]==-1 && f[X][Y]==0)
{
d[X][Y]=d[t.first][t.second]+1;
q.push({X,Y});
}
}
}
return d[n][m];
}
int main()
{
memset(d,-1,sizeof d);
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>f[i][j];
cout<<bfs();
return 0;
}