题目解释&数据范围
给定一张NM的地图，地图中有1个男孩，1个女孩和2个鬼。
字符“.”表示道路，字符“X”表示墙，字符“M”表示男孩的位置，字符“G”表示女孩的位置，字符“Z”表示鬼的位置。
男孩每秒可以移动3个单位距离，女孩每秒可以移动1个单位距离，男孩和女孩只能朝上下左右四个方向移动。
每个鬼占据的区域每秒可以向四周扩张2个单位距离，并且无视墙的阻挡，也就是在第k秒后所有与鬼的曼哈顿距离不超过2k的位置都会被鬼占领。
注意： 每一秒鬼会先扩展，扩展完毕后男孩和女孩才可以移动。
求在不进入鬼的占领区的前提下，男孩和女孩能否会合，若能会合，求出最短会合时间。
输入格式
第一行包含整数T，表示共有T组测试用例。
每组测试用例第一行包含两个整数N和M，表示地图的尺寸。
接下来N行每行M个字符，用来描绘整张地图的状况。（注意：地图中一定有且仅有1个男孩，1个女孩和2个鬼
输出格式
每个测试用例输出一个整数S，表示最短会合时间。
如果无***合则输出-1。
每个结果占一行。
数据范围
1<n,m<800
思路:我们把鬼的行动直接用距离公式计算即可,一旦我这个点的距离和鬼的距离<2step的话,这个点就不可以走.那么鬼的就处理了,然后我们开两个队列,一个存boy的可行解,另一个存girl的可行解,一旦这个地方不合法了,就不扩展了,假如合法就扩展,我们用st[x][y]的1和2分别表示男孩和女孩,一旦男孩可以走的地方出现女孩,或者女孩可以走的地方出现男孩就直接return step;
代码实现:

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
typedef pair<int,int> pi;
const int N=805;
int n,m,step=0;
char an[N][N];
int st[N][N];
pi ghost[2];
bool ck(int x,int y)
{
    if(x<0||x>=n||y<0||y>=m||an[x][y]=='X') return false;
    for(int i=0;i<2;i++)
    {
        if(abs(ghost[i].f-x)+abs(ghost[i].s-y)<=step*2) return false;
    }
    return true;
} 

int bfs()
{
    memset(st,0,sizeof st);
    step=0;
    int dx[4]={-1,1,0,0};int dy[4]={0,0,1,-1};
    pi boy,girl;int g=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(an[i][j]=='M')      { boy={i,j}; }//男孩
            else if(an[i][j]=='G') { girl={i,j}; }//女孩
            else if(an[i][j]=='Z') { ghost[g++]={i,j}; }//鬼
        }
    }
    queue<pi>qb,qg;
    qb.push(boy);qg.push(girl);
    while(qb.size()||qg.size())
    {
        step++;
        for(int i=0;i<3;i++)
        {
            for(int j=0,len=qb.size();j<len;j++)
            {
                auto t=qb.front();
                qb.pop();
                if(!ck(t.f,t.s)) continue;
                for(int k=0;k<4;k++)
                {
                    if(ck(t.f+dx[k],t.s+dy[k]))
                    {
                        if(!st[t.f+dx[k]][t.s+dy[k]])
                        {
                            st[t.f+dx[k]][t.s+dy[k]]=1;
                            qb.push({t.f+dx[k],t.s+dy[k]});
                        }
                        else if(st[t.f+dx[k]][t.s+dy[k]]==2)  return step;//假如这个点属于girl.拿出来的点boy肯定染色了的
                    }
                }
            }
        }//扩展3次
        for(int i=0,len=qg.size();i<len;i++)
        {
            auto t=qg.front();
            qg.pop();
            if(!ck(t.f,t.s)) continue;
            for(int k=0;k<4;k++)
            {
                if(ck(t.f+dx[k],t.s+dy[k]))
                {
                    if(!st[t.f+dx[k]][t.s+dy[k]])
                    {
                      st[t.f+dx[k]][t.s+dy[k]]=2;
                      qg.push({t.f+dx[k],t.s+dy[k]});
                    }
                    else if(st[t.f+dx[k]][t.s+dy[k]]==1)  return step;//假如这个点属于boy.拿出来的点girl肯定染色了的
                }
            }
        }
    }
    return -1;
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        for(int i=0;i<n;i++) cin>>an[i];
        cout<<bfs()<<endl;
    }
    return 0;
}