题目传送门

#include<bits/stdc++.h>
#define int long long
using namespace std;
char arr[801][801];
int cango[801][801];
int n,m;
bool canlive(pair<int,int> a1,pair<int,int> a2,int sz){
	return (abs(a1.first-a2.first)+abs(a1.second-a2.second)>sz);
}
bool inmap(pair<int,int> s){
	return (s.first>=1&&s.first<=n&&s.second>=1&&s.second<=m);
}
struct node{
	pair<int,int> e;
	int t;
	int gui;
	int delay;
};
const int mov[5][2]={{1,0},{-1,0},{0,1},{0,-1},{0,0}};
bool vis[801][801];
bool viss[801][801][4];
void func(){
	cin>>n>>m;
	memset(arr,0,sizeof arr);
	memset(cango,0x7f,sizeof cango);
	memset(vis,0,sizeof vis);
	memset(viss,0,sizeof viss);
	int ex,ey,gx,gy,g1x=-1919,g1y,g2x,g2y;//e:男友	g:女友	g1,g2:鬼魂
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
		cin>>arr[i][j];
		if(arr[i][j]=='M')ex=i,ey=j;
		if(arr[i][j]=='G')gx=i,gy=j;
		if(arr[i][j]=='Z'){
			if(g1x==-1919){
				g1x=i,g1y=j;
			}
			else{
				g2x=i,g2y=j;
			}
		}
	}
	cango[g1x][g2x]=0;
	pair<int,int>g1={g1x,g1y};
	pair<int,int>g2={g2x,g2y};
	queue<node>boy;
	queue<node>girl;
	boy.push({{ex,ey},0,2});
	girl.push({{gx,gy},0,2});
	while(!boy.empty()){
		node t=boy.front();
		boy.pop();
		if(t.t<cango[t.e.first][t.e.second]&&t.delay==0)cango[t.e.first][t.e.second]=t.t;
		if(canlive(t.e,g1,t.gui)&&canlive(t.e,g2,t.gui)){
			for(int i=0;i<5;i++){
				node nw={{t.e.first+mov[i][0],t.e.second+mov[i][1]},t.t,t.gui,t.delay};
				if(arr[nw.e.first][nw.e.second]!='X'&&inmap(nw.e)){
					nw.delay++;
					
					if(canlive(nw.e,g1,nw.gui)&&canlive(nw.e,g2,nw.gui)){
						if(nw.delay>=3)nw.t++,nw.gui+=2,nw.delay=0;
						if(viss[nw.e.first][nw.e.second][nw.delay]==1)continue;
						boy.push(nw);
						viss[nw.e.first][nw.e.second][nw.delay]=1;
					}
				}
			}
		}
	}
	int ans=1145555000114455;
	while(!girl.empty()){
		node t=girl.front();
		girl.pop();
		if(canlive(t.e,g1,t.gui)&&canlive(t.e,g2,t.gui)){
			for(int i=0;i<5;i++){
				node nw={{t.e.first+mov[i][0],t.e.second+mov[i][1]},t.t+1,t.gui+2,0};
				if(vis[nw.e.first][nw.e.second]==0&&canlive(nw.e,g1,t.gui)&&canlive(nw.e,g2,t.gui)&&arr[nw.e.first][nw.e.second]!='X'&&inmap(nw.e)){
					girl.push(nw);
					ans=min(max(nw.t,cango[nw.e.first][nw.e.second]),ans);
					vis[nw.e.first][nw.e.second]=1;
				}
			}
		}
	}
	if(ans!=1145555000114455){
		cout<<ans<<"\n";
		return;
	}
	cout<<"-1\n";
}
signed main(){
	int T;
	cin>>T;
	while(T--)func();
}