bfs.rar_hdu

#include<stdio.h> #include<string.h> #include<math.h> #include<queue> #include<iostream> using namespace std; #define inf 100000000 struct Nodes{ int x,y,step; }; queue<Nodes>q; int s[4][810][810],cnt; int n,m,xx[5]={0,1,0,-1},yy[5]={1,0,-1,0}; char map[810][810]; int gx,gy,bx,by,vx[2],vy[2]; int minstep; int maxx(int x,int y) { return x>y?x:y; } int minn(int x,int y) { return x<y?x:y; } int check2(int sx,int sy) { if(sx>=0&&sx<n&&sy>=0&&sy<m&&map[sx][sy]!='X'&&map[sx][sy]!='Z')return 1; return 0; } void bfs2(int sx,int sy) { int i,j,x,y; Nodes num1,num2; num1.x=sx;num1.y=sy; num1.step=0;s[cnt][sx][sy]=0; while(!q.empty())q.pop(); q.push(num1); while(!q.empty()){ num1=q.front(); q.pop(); if(s[0][num1.x][num1.y]<=(num1.step)/3+1)continue; for(i=0;i<4;i++){ num2.x=num1.x+xx[i];num2.y=num1.y+yy[i]; if(check2(num2.x,num2.y)){ num2.step=num1.step+1; if(s[0][num2.x][num2.y]>(num2.step+2)/3&&s[cnt][num2.x][num2.y]>num2.step){ s[cnt][num2.x][num2.y]=num2.step; q.push(num2); } } } } return ; } void bfs3(int sx,int sy) { int i,j,x,y,kk; Nodes num1,num2; num1.x=sx;num1.y=sy; num1.step=0;s[cnt][sx][sy]=0; while(!q.empty())q.pop(); q.push(num1); while(!q.empty()){ num1=q.front(); q.pop(); if(num1.step+1>=s[0][num1.x][num1.y])continue; for(i=0;i<4;i++){ x=num1.x+xx[i];y=num1.y+yy[i]; if(check2(x,y)){ if(s[0][x][y]<=num1.step+1)continue; if(s[cnt][x][y]>num1.step+1){ s[cnt][x][y]=num1.step+1; num2.x=x;num2.y=y; num2.step=num1.step+1; q.push(num2); } } } } return ; } int main() { int t,i,j,k,kk,kkk; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); k=0; for(i=0;i<n;i++){ scanf("%s",map[i]); for(j=0;j<m;j++){ if(map[i][j]=='M'){ bx=i;by=j; } if(map[i][j]=='G'){ gx=i;gy=j; } if(map[i][j]=='Z'){ vx[k]=i;vy[k]=j; k++; } s[0][i][j]=s[1][i][j]=s[2][i][j]=inf; } } minstep=inf; for(i=0;i<n;i++){ for(j=0;j<m;j++){ kkk=inf; for(kk=0;kk<k;kk++){ kkk=minn(kkk,abs(vx[kk]-i)+abs(vy[kk]-j)); } s[0][i][j]=(kkk+1)/2; } } cnt=1; bfs2(bx,by); cnt++; bfs3(gx,gy); cnt++; for(i=0;i<n;i++) for(j=0;j<m;j++) if((s[1][i][j]+2)/3<s[0][i][j]&&s[2][i][j]<s[0][i][j]){ kkk=maxx((s[1][i][j]+2)/3,s[2][i][j]); if(kkk<minstep)minstep=kkk; } if(minstep==inf)printf("-1\n"); else printf("%d\n",minstep); } return 0; }