- #include<iostream>
- typedef struct node
- {
- int x;
- int y;
- }node;
- int sx,sy,ex,ey;
- node point[100000];
- int data[50][50];
- int hang,lie;
- int k;
- int dx[4]={-1,0,1,0};
- int dy[4]={0,1,0,-1};
- int min=-1;
- int flag=1;
- int a[50][50];
- void bfs(int p)
- {
- int tou=0;
- int wei=1;
- point[tou].x=sx;
- point[tou].y=sy;
- data[sx][sy]=4;
- while(tou<wei)
- {
- if(point[tou].x==ex&&point[tou].y==ey)
- { flag=0;
- min=p;
- break;
- }
- for(int i=0;i<4;i++)
- { int q=i;
- if(i==0||i==2)
- {
- int nx=point[tou].x;
- int ny=point[tou].y;
- for(int i=0;i<=p;i++)
- {
- nx=nx+dx[q];
- ny=ny+dy[q];
- if(nx>=0&&nx<hang&&ny>=0&&ny<lie&&data[nx][ny]!=4&&data[nx][ny]!=0)
- { data[nx][ny]=4;
- point[wei].x=nx;
- point[wei].y=ny;
- wei++;
- break;
- }
- }
- }
- if(i==1||i==3)
- {
- int nx=point[tou].x+dx[i];
- int ny=point[tou].y+dy[i];
- if(nx>=0&&nx<hang&&ny>=0&&ny<lie&&data[nx][ny]!=4&&data[nx][ny]!=0)
- {
- data[nx][ny]=4;
- point[wei].x=nx;
- point[wei].y=ny;
- wei++;
- }
- }
- }
- tou++;
- }
- }
- int main()
- {
- freopen("input.txt","r",stdin);
- scanf("%d",&k);
- while(k--)
- { flag=1;
- scanf("%d",&hang);
- scanf("%d",&lie);
- for(int i=0;i<hang;i++)
- { for(int j=0;j<lie;j++)
- {scanf("%d",&data[i][j]);
- //scanf("%d",&a[i][j]);
- if(data[i][j]==2)
- { data[i][j]=4;
- sx=i;
- sy=j;
- }
- if(data[i][j]==3)
- {
- ex=i;
- ey=j;
- }
- }
- }
- for(int i=0;i<hang;i++)
- for(int j=0;j<lie;j++)
- a[i][j]=data[i][j];
- for(int i=0;i<hang;i++)
- {for(int j=0;j<lie;j++)
- printf("%d",data[i][j]);
- printf("\n");}
- printf("\n");
- for(int i=0;i<lie;i++)
- {
- if(flag)
- {
- for(int l=0;l<hang;l++)
- for(int k=0;k<lie;k++)
- {
- data[l][k]=a[l][k];
- }
- bfs(i);
- }
- }
- for(int i=0;i<hang;i++)
- {for(int j=0;j<lie;j++)
- printf("%d",data[i][j]);
- printf("\n");}
- printf("%d",min);
- }
- }
来源: http://www.bubuko.com/infodetail-1947810.html