题目描述
农场主John把农场分为了一个 r 行 c 列的矩阵，并发现奶牛们无法通过其中一些区域。此刻，Bessie 位于坐标为 (1,1) 的区域，并想到坐标为 (r,c) 的牛棚享用晚餐。她知道，以她所在的区域为起点，每次移动至相邻的四个区域之一，如果奶牛吃不到饭就会大哭。
输入
第一行两个整数 r,c。
接下来 r 行，每行 c 个字符，表示 Bessie 能否通过相应位置的区域。字符只可能是 0 或 1。
0 表示 Bessie 可以通过该区域。
1 表示 Bessie 无法通过该区域。
输出
1行，输出Bessie的最少移动次数或-1
样例输入
3 3 001 101 100
样例输出
4
Code:
#include<bits/stdc++.h>
using namespace std;
int r,c,dx[4]={0,0,1,-1},dy[4]={1,-1,0,0},ans=INT_MAX;
char mp[1005][1005];
bool vis[1005][1005];
struct node{
int x,y,step;
};
void bfs(int x,int y,int step){
queue<node>que;
node temp={x,y,step};
vis[x][y]=true;
que.push(temp);
while(!que.empty()){
node now=que.front();
que.pop();
for(int i=0;i<4;i++){
int xx=now.x+dx[i],yy=now.y+dy[i];
if(xx<1||xx>r||yy<1||yy>c||vis[xx][yy]==true||mp[xx][yy]=='1'){
continue;
}
vis[xx][yy]=true;
node temp={xx,yy,now.step+1};
que.push(temp);
if(xx==r&&yy==c){
ans=min(ans,temp.step);
}
}
}
if(ans!=INT_MAX){
cout<<ans;
}else{
cout<<-1;
}
}
int main(){
cin>>r>>c;
for(int i=1;i<=r;i++){
for(int j=1;j<=c;j++){
cin>>mp[i][j];
}
}
bfs(1,1,0);
return 0;
}