时间限制 : 3000 MS 空间限制 : 65536 KB
评测说明 : 1s
输入格式
第一行,两个空格间隔的整数n和m
接下来是一个n*m的矩阵,用空格做间隔
输出格式
一个整数,表示最小的步数。
样例输入
5 8
3 0 0 0 0 2 0 3
2 0 0 2 3 0 2 0
0 2 0 2 0 3 0 2
0 1 0 2 0 0 0 0
0 0 0 0 0 0 0 3
样例输出
6
include[HTML_REMOVED]
using namespace std;
struct node{
int x,y,step;
}r;
int a[1010][1010];
int dx[4]={-1,1,0,0},dy[4]={0,0,1,-1};
queue[HTML_REMOVED]q;
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i)
for(int j=1;j<=m;j){
cin>>a[i][j];
if(a[i][j]==1)r.x=i,r.y=j,a[i][j]=2;
}
r.step=0;q.push(r);
while(!q.empty()){
r=q.front();node t;
for(int i=0;i<=3;i++){
int xx=dx[i]+r.x,yy=dy[i]+r.y;
if(a[xx][yy]==3){
cout<[HTML_REMOVED]=1&&xx<=n&&yy>=1&&yy<=m&&a[xx][yy]==0){
a[xx][yy]=2;
t.x=xx,t.y=yy,t.step=r.step+1;
q.push(t);
}
}q.pop();
}
cout<<”0”;return 0;
}