#include <bits/stdc++.h>

using namespace std;

#define ABS(x) ((x) < 0 ? -(x) : (x))
#define dist(a, b, c, d) ABS((a) - (c)) + ABS((b) - (d))

constexpr int N = 1010;

constexpr int dx[4] = {-1, 0, 0, 1};
constexpr int dy[4] = {0, -1, 1, 0};

struct point {
	int x, y;
	point() = default;
	point(int x, int y): x(x), y(y) {}
};

int n, m;

namespace ghost {
	struct _ghost_t : point {
		_ghost_t(int x, int y): point(x, y) {}
	};
	
	vector<_ghost_t> _ghost;
	
	void clear() {
		_ghost.clear();
	}
	
	void insert(int x, int y) {
		_ghost.emplace_back(x, y);
	}
	
	// time t, kill (x, y) ?
	bool kill_time(int t, int x, int y) {
		for (auto i : _ghost) {
			int d = dist(x, y, i.x, i.y);
			if (d <= t * 2) return true;
		}
		return false;
	}
}

int mp[N][N]; // 0 none, -1 wall, 1 bol, 2 girl, 3 wow

struct node : point {
	int t; // time
	node(int x, int y, int t): point(x, y), t(t) {}
};

struct emm : point {
	int dis;
	emm(int x, int y, int dis): point(x, y), dis(dis) {}
};

void welcome() {
	cin >> n >> m;
	ghost::clear();
	queue<node> q;
	for (int i = 1; i <= n; ++i) {
		string s; cin >> s;
		for (int j = 1; j <= n; ++j) {
			char c = s[j - 1];
			if (c == 'X') mp[i][j] = -1;
			else if (c == 'Z') ghost::insert(i, j);
			else if (c == 'M') mp[i][j] = 1, q.emplace(i, j, 1);
			else if (c == 'G') mp[i][j] = 2, q.emplace(i, j, 1);
			else mp[i][j] = 0;
		}
	}
	while (!q.empty()) {
		auto u = q.front(); q.pop();
		if (ghost::kill_time(u.t, u.x, u.y)) continue;
		int tp = mp[u.x][u.y];
		int delta = (tp == 1) ? 3 : 1; 
		//int delta = (2 - tp) * 2 + 1;
		queue<emm> qt;
		qt.emplace(u.x, u.y, 0);
		while (!qt.empty()) {
			auto v = qt.front(); qt.pop();
			if (v.dis >= delta) continue;
			for (int k = 0; k < 4; ++k) {
				int tx = v.x + dx[k], ty = v.y + dy[k];
				if (tx <= 0 || tx > n || ty <= 0 || ty > m) continue;
				if (mp[tx][ty] == -1 || mp[tx][ty] == tp) continue;
				if (ghost::kill_time(u.t, tx, ty)) continue;
				mp[tx][ty] |= tp;
				if (mp[tx][ty] == 3) {
					cout << u.t << endl;
					return;
				}
				q.emplace(tx, ty, u.t + 1);
				qt.emplace(tx, ty, v.dis + 1);
			}
		}
	}
	cout << -1 << endl;
	return;
}

signed main() {
	//ios::sync_with_stdio(false);
	//cin.tie(nullptr), cout.tie(nullptr);
	int T; cin >> T; while (T--) welcome();
	return 0;
}

调不出来了/ll

思路是一个双向 BFS 拓展两个 xql。

然后拓展的时候小帅哥能走三步，这三布又写了一个 BFS 去拓展。

thx.