#include #include <math.h> #include #include <stdio.h> #include #include <string.h> #include 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 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; } }