[伪题解]
题目描述
八十高龄的邓大爷在大街上摔倒了，因为众所周知的原因围观的路人都不敢去救助。恰好何老板下班路过，一向助人为乐的他赶紧抱起邓大爷往医院跑。但好心的何老板面临着一个问题，城市里面有很多医院，到底哪家医院最近呢？
城市地图用一个由数字0,1,2,3构成的n*m矩阵表示(n,m<=1000)。数字0表示可以行走的道路或空地。数字1表示邓大爷摔倒的位置。数字2表示不可通过的建筑物或障碍物。数字3表示医院。
何老板只能延上下左右四个方向移动，每走一步的距离是1。问到最近的医院需要走多少步？（地图中至少有一个可到达的医院）
输入格式
第一行，两个空格间隔的整数n和m
接下来是一个n*m的矩阵，用空格做间隔
输出格式
一个整数，表示最小的步数。
#include<iostream> #include<queue> using namespace std; struct node{int x,y,step;}noww; int mapp[1010][1010]; int dx[4]={-1,1,0,0},dy[4]={0,0,1,-1};//增量数组 queue<node>q; int main(){ int n,m;cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ cin>>mapp[i][j]; if(mapp[i][j]==1)noww.x=i,noww.y=j,mapp[i][j]=2; } noww.step=0;q.push(noww); while(!q.empty()){ noww=q.front();node t; for(int i=0;i<=3;i++){ int xx=dx[i]+noww.x,yy=dy[i]+noww.y; if(mapp[xx][yy]==3){cout<<noww.step+1;return 0;} if(xx>=1 && xx<=n && yy>=1 && yy<=m && mapp[xx][yy]==0){ mapp[xx][yy]=2; t.x=xx,t.y=yy,t.step=noww.step+1; q.push(t); } }q.pop(); } cout<<"0";return 0; }
1234567891011121314151617181920212223242526272829
