AcWing 844. 走迷宫
原题链接
简单
作者:
simoni
,
2021-08-22 16:50:16
,
所有人可见
,
阅读 183
#include<bits/stdc++.h>
using namespace std;
int step[110][110];
bool d[110][110];
int n,m;
int bfs(){
memset(step,-1,sizeof step);
queue<pair<int,int>>duilie;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
duilie.push({0,0});
step[0][0]=0;
while(duilie.size()){
auto t=duilie.front();
duilie.pop();
if(t.first==n-1&&t.second==m-1)return step[n-1][m-1];//在此时即可退出bfs()
for(int i=0;i<4;i++){
int x=t.first+dx[i];
int y=t.second+dy[i];
if(x>=0 && x<n &&y>=0 && y<m &&step[x][y]==-1 &&d[x][y]==0){
step[x][y]=step[t.first][t.second]+1;
duilie.push({x,y});
}
}
}
// return step[n-1][m-1];
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)cin>>d[i][j];
cout<<bfs();
}