C++ 代码
#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#include<cstring>
using namespace std;
#define go(i,a,b) for(int i=a;i<=b;++i)
#define com(i,a,b) for(int i=a;i>=b;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pai;
const int inf=0x3f3f3f3f,N=808;
const int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
int n,m,gx,gy,bx,by,px,py,qx,qy,t;
bool v1[N][N],v2[N][N],flag;
char s[N][N];
queue<pai>q1,q2;
inline void read(int &x){
x=0;char f=1,c=getchar();
while(!isdigit(c)){ if(c=='-') f=-1; c=getchar(); }
while(isdigit(c)){ x=x*10+c-'0'; c=getchar(); }
x*=f;
}
bool pd(int x,int y){
if(x<1||x>n||y<1||y>m) return 0;
if(s[x][y]=='X') return 0;
if(abs(x-px)+abs(y-py)<=2*t) return 0;
if(abs(x-qx)+abs(y-qy)<=2*t) return 0;
return 1;
}
void work(queue<pai> &q,bool v1[][N],bool v2[][N]){//队列一定要加引用才能修改
int s=q.size();
go(i,1,s){
pai now=q.front();q.pop();
int x=now.fi,y=now.se;
if(!pd(x,y)) continue;
go(k,0,3){
int nx=x+dx[k],ny=y+dy[k];
if((!pd(nx,ny))||v1[nx][ny]) continue;
v1[nx][ny]=1;
if(v2[nx][ny]){
flag=1;
return;
}
q.push(mp(nx,ny));
}
}
}
int bfs(){
while(!q1.empty()) q1.pop();
while(!q2.empty()) q2.pop();
px=t=flag=0;
mem(v1,0);
mem(v2,0);
go(i,1,n)
go(j,1,m)
if(s[i][j]=='M')
bx=i,by=j;
else if(s[i][j]=='G')
gx=i,gy=j;
else if(s[i][j]=='Z'){
if(!px) px=i,py=j;
else qx=i,qy=j;
}
q1.push(mp(bx,by)),q2.push(mp(gx,gy));
while((!q1.empty())||(!q2.empty())){
++t;
work(q1,v1,v2);
work(q1,v1,v2);
work(q1,v1,v2);
work(q2,v2,v1);
if(flag) return t;
}
return -1;
}
int main(){
//freopen("input.txt","r",stdin);
int T;read(T);
while(T--){
read(n),read(m);
go(i,1,n) scanf("%s",s[i]+1);
printf("%d\n",bfs());
}
return 0;
}