#include <queue> #include <math.h> #include <stack> #include <stdio.h> #include <iostream> #include <string.h> #include <algorithm> using namespace std; #define LL long long const int N = 805; int n , m; struct node { int x, y; }gui[2]; int dx[] = {1,-1,0,0}; int dy[] = {0,0,1,-1}; char dmap[N][N]; int st[N][N]; bool cheak(int x, int y , int time) { if(x < 0 || y < 0 || x >= n || y >= m || dmap[x][y] == 'X') return false; for(int i = 0 ; i < 2; i++) { if(abs( x - gui[i].x ) + abs(y - gui[i].y) <= time * 2) return false; } return true; } int bfs() { memset(st,0,sizeof(st)); queue<node> mm , gg; int cnt = 0; for(int i = 0 ; i < n ; i++) for(int j = 0 ; j< m ; j++) { if(dmap[i][j] == 'M') { st[i][j] = 2; mm.push((node){i,j}); } else if(dmap[i][j] == 'G') { st[i][j] = 1; gg.push((node){i,j}); } else if(dmap[i][j] == 'Z') gui[cnt++] = (node){i,j}; } int time = 0; node p; while(!mm.empty() || !gg.empty()) { time++; for(int i = 0 ; i < 3 ; i++) { for(int j = 0 ,len = mm.size() ; j < len ; j++) { p = mm.front(); mm.pop(); if(cheak(p.x,p.y,time)==false ) continue; for(int k = 0 ; k < 4; k++) { int x = p.x + dx[k]; int y = p.y + dy[k]; if(cheak(x,y,time)) { if(st[x][y] == 1) return time; if(st[x][y] == 0) { st[x][y] = 2; mm.push((node){x,y}); } } } } } for(int i = 0 , len = gg.size() ; i < len ; i++) { p = gg.front(); gg.pop(); if(cheak(p.x,p.y,time)==false ) continue; for(int k = 0 ; k < 4; k++) { int x = p.x + dx[k]; int y = p.y + dy[k]; if(cheak(x,y,time)) { if(st[x][y] == 2) return time; if(st[x][y] == 0) { st[x][y] = 1; gg.push((node){x,y}); } } } } } return -1;

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

C++ :

/*****************************************
Problem Name  : 
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 805;
int n , m;
struct node 
{
	int x, y;
}gui[2];
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
char dmap[N][N];
int st[N][N];
bool cheak(int x, int y , int time)
{
	if(x < 0 || y < 0 || x >= n || y >= m || dmap[x][y] == 'X')
		return false;
	for(int i = 0 ; i < 2; i++)
	{
		if(abs( x - gui[i].x ) + abs(y - gui[i].y) <= time * 2)
			return false;
	}
	return true;
}
int bfs()
{
	memset(st,0,sizeof(st));
	queue<node> mm , gg;
	int cnt = 0;
	for(int i = 0 ; i < n ; i++)
		for(int j = 0 ; j< m ; j++)
		{
			if(dmap[i][j] == 'M')
			{
				st[i][j] = 2;
				mm.push((node){i,j});
			}
			else if(dmap[i][j] == 'G')
			{
				st[i][j] = 1;
				gg.push((node){i,j});
			}
			else if(dmap[i][j] == 'Z')
				gui[cnt++] = (node){i,j};
		}
	int time = 0;
	node p;
	while(!mm.empty() || !gg.empty())
	{
		time++;
		for(int i = 0 ; i < 3 ; i++)
		{
			for(int j = 0 ,len = mm.size() ; j < len ; j++)
			{
				p = mm.front();
				mm.pop();
				if(cheak(p.x,p.y,time)==false )
					continue;
				for(int k = 0 ; k < 4; k++)
				{
					int x = p.x + dx[k];
					int y = p.y + dy[k];
					if(cheak(x,y,time))
					{
						if(st[x][y] == 1)
							return time;
						if(st[x][y] == 0)
						{
							st[x][y] = 2;
							mm.push((node){x,y});
						}
					}
				}
			}
		}
		for(int i = 0 , len = gg.size() ; i < len ; i++)
		{
			p = gg.front();
			gg.pop();
			if(cheak(p.x,p.y,time)==false )
				continue;
			for(int k = 0 ; k < 4; k++)
			{
				int x = p.x + dx[k];
				int y = p.y + dy[k];
				if(cheak(x,y,time))
				{
					if(st[x][y] == 2)
						return time;
					if(st[x][y] == 0)
					{
						st[x][y] = 1;
						gg.push((node){x,y});
					}
				}
			}
		}
	}
	return -1;

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