6.噩梦

原题：https://www.acwing.com/problem/content/description/179/

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

#define x first
#define y second
typedef pair<int,int> PII;

PII boy,girl,gt[2];
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
const int N=810;
int st[N][N];
int n,m,cnt;
char g[N][N];

bool check(int x,int y,int t)
{
    if(x<0||x>=n||y<0||y>=m||g[x][y]=='X') return false;
    for(int i=0;i<cnt;i++)
    {
        if(abs(gt[i].x-x)+abs(gt[i].y-y)<=2*t) return false;
    }
    return true;
}

int bfs()
{
    cnt=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            if(g[i][j]=='M') boy={i,j};
            else if(g[i][j]=='G') girl={i,j};
            else if(g[i][j]=='Z') gt[cnt++]={i,j};
        }
    queue<PII> q1,q2;
    q1.push(boy),q2.push(girl);
    int step=0;
    memset(st,0,sizeof st);
    while(q1.size()||q2.size())
    {
        step++;
        for(int i=0;i<3;i++)
        {
            for(int j=0,len=q1.size();j<len;j++)
            {
                auto t=q1.front();
                q1.pop();
                if(!check(t.x,t.y,step)) continue;
                for(int k=0;k<4;k++)
                {
                    int x=dx[k]+t.x,y=dy[k]+t.y;
                    if(!check(x,y,step)) continue;
                    if(st[x][y]==2) return step;
                    if(st[x][y]==0){
                        st[x][y]=1;
                        q1.push({x,y});
                    }
                }
            }
        }
        for(int j=0,len=q2.size();j<len;j++)
        {
            auto t=q2.front();
            q2.pop();
            if(!check(t.x,t.y,step)) continue;
            for(int k=0;k<4;k++)
            {
                int x=dx[k]+t.x,y=dy[k]+t.y;
                if(!check(x,y,step)) continue;
                if(st[x][y]==1) return step;
                if(st[x][y]==0){
                    st[x][y]=2;
                    q2.push({x,y});
                }
            }
        }
    }
    return -1;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)
            scanf("%s",&g[i]);
        int t=bfs();
        printf("%d\n",t);
    }
    return 0;
}