C++14(g++5.4) 解法, 执行用时: 38ms, 内存消耗: 4728K, 提交时间: 2020-04-24 12:39:59

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
      
using namespace std;
   
#define N               1000
#define MP(i,j)         make_pair(i,j)
typedef pair<int,int>   PII;

int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
int gx[2], gy[2];

int     n, m, T, num, cnt;
bool    M[N][N], G[N][N];
string  S[N];

bool check(int i, int j) {
    if (i < 0 || i >= n || j < 0 || j >= m || S[i][j] == 'X') return false;
    for (int k = 0; k < cnt; k++) {
        if (abs(i-gx[k]) + abs(j-gy[k]) <= 2 * num) {
            return false;
        }
    }
    return true;
}

bool expand(queue<PII>& que, queue<PII>& tmp, int step, bool A[][N], bool B[][N]) {
    PII node;
    int u, v, i, j;
    while (step--) {
        while (!que.empty()) {
            node = que.front(); que.pop();
            u = node.first; v = node.second;
            if (!check(u, v)) continue;
            for (int k = 0; k < 4; k++) {
                i = u + dx[k]; j = v + dy[k];
                if (!check(i, j) || A[i][j]) continue;
                if (B[i][j])                 return true;
                tmp.push(MP(i, j));
                A[i][j] = true;
            }
        }
        swap(que, tmp);
    }
    return false;
}

int bfs() {
    memset(M, 0, sizeof(M));
    memset(G, 0, sizeof(G));
    cnt = num = 0;
        
    queue<PII> mue, gue, mtm, gtm;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (S[i][j] == 'Z') { gx[cnt] = i; gy[cnt] = j; cnt++; }
            if (S[i][j] == 'M') mue.push(MP(i, j));
            if (S[i][j] == 'G') gue.push(MP(i, j));
        }
    }

    while (!mue.empty() || !gue.empty()) {
        num++;
        if (!mue.empty() && expand(mue, mtm, 3, M, G)) return num;
        if (!gue.empty() && expand(gue, gtm, 1, G, M)) return num;
    }
    return -1;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
    cin >> T;
    while (T--) {
        cin >> n >> m;
        for (int i = 0; i < n; i++) cin >> S[i];
        cout << bfs() << endl;
    }
    return 0;
}

C++ 解法, 执行用时: 19ms, 内存消耗: 2336K, 提交时间: 2021-09-13 13:00:21

#include<bits/stdc++.h>
using namespace std;
const int N=810;
int t,n,m,bx,by,gx,gy,px,py,qx,qy,dx[4]={1,-1,0,0},dy[4]={0,0,1,-1},ans;
bool v[2][N][N],flag;
char s[N][N];
queue<pair<int,int> >q[2];
bool ok(int x,int y,int k){
	if(x<1||x>n||y<1||y>m) return 0;
	if(abs(x-px)+abs(y-py)<=2*k||abs(x-qx)+abs(y-qy)<=2*k) return 0;
	return s[x][y]!='X';
}
bool bfs(int t){
	int sz=q[t].size();
	for(int i=1;i<=sz;i++){
		int x=q[t].front().first,y=q[t].front().second;q[t].pop();
		if(!ok(x,y,ans)) continue;
		for(int k=0;k<4;k++){
			int nx=x+dx[k],ny=y+dy[k];
			if(ok(nx,ny,ans)&&!v[t][nx][ny]){
				if(v[!t][nx][ny]) return 1; 
				v[t][nx][ny]=1,q[t].push(make_pair(nx,ny));
			}
		}
	}
	return 0;
}
signed main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m),ans=px=0,flag=0;
		for(int i=1;i<=n;i++){
			scanf("%s",s[i]+1);
			for(int j=1;j<=m;j++){
				if(s[i][j]=='M') bx=i,by=j;
				if(s[i][j]=='G') gx=i,gy=j; 
				if(s[i][j]=='Z') !px?(px=i,py=j):(qx=i,qy=j);
			}
		}
		memset(v,0,sizeof(v));
		v[0][bx][by]=1,q[0].push(make_pair(bx,by));
		v[1][gx][gy]=1,q[1].push(make_pair(gx,gy));
		while(q[0].size()||q[1].size()){
			ans++,bfs(0),bfs(0),bfs(0);
			if(bfs(1)){flag=1,printf("%d\n",ans);break;} 
		}
		while(q[0].size()) q[0].pop();
		while(q[1].size()) q[1].pop();
		if(!flag) puts("-1");
	}
	return 0;
}