給定一張 N×M 的地圖，地圖中有 1 個男孩，1 個女孩和 2 個鬼。
字符 . 表示道路，字符 X 表示牆，字符 M 表示男孩的位置，字符 G 表示女孩的位置，字符 Z 表示鬼的位置。
男孩每秒可以移動 3 個單位距離，女孩每秒可以移動 1 個單位距離，男孩和女孩只能朝上下左右四個方向移動。
每個鬼占據的區域每秒可以向四周擴張 2 個單位距離，並且無視牆的阻擋，也就是在第 k 秒後所有與鬼的曼哈頓距離不超過 2k 的位置都會被鬼占領。
注意： 每一秒鬼會先擴展，擴展完畢後男孩和女孩才可以移動。
求在不進入鬼的占領區的前提下，男孩和女孩能否會合，若能會合，求出最短會合時間。
輸入格式
第一行包含整數 T，表示共有 T 組測試用例。
每組測試用例第一行包含兩個整數 N 和 M，表示地圖的尺寸。
接下來 N 行每行 M 個字符，用來描繪整張地圖的狀況。（注意：地圖中一定有且僅有 1 個男孩，1 個女孩和 2 個鬼）
輸出格式
每個測試用例輸出一個整數 S，表示最短會合時間。
如果無法會合則輸出 −1。
每個結果占一行。
數據范圍
1<n,m<800
輸入樣例：
3
5 6
XXXXXX
XZ..ZX
XXXXXX
M.G...
......
5 6
XXXXXX
XZZ..X
XXXXXX
M.....
..G...
10 10
..........
..X.......
..M.X...X.
X.........
.X..X.X.X.
.........X
..XX....X.
X....G...X
...ZX.X...
...Z..X..X
輸出樣例：
1
1
-1拿到題目後首先思考用什麼算法：本題特征很明顯 是一個地圖類型的題 自然而然想到使用bfs求解
但我們發現本題最棘手的地方是男生，女生和鬼每一輪都需要擴展，這該怎麼辦呢，我們進一步發現，其實鬼的擴展並不需要展示出來，只需要男女生每次擴展時，檢測一下當前點是否是在鬼的擴展范圍之內即可
擴展男生女生就較為簡單了 只需要正常先擴展一個再擴展另一個即可 每當男生/女生擴展到一個格子 都要判斷這個格子能不能走 如果能走 看看是否被女生/男生擴展過 若是擴展過說明他們可以相遇 可以直接返回答案了。否則標記為男生/女生走過該點
具體步驟如下 ：
我們在bfs中按時間t從 1 開始枚舉。
如果男孩和女孩都不能再繼續擴展，則跳出枚舉。
對於男孩，每次擴展三步，並標記擴展到的格子。
如果某個能擴展的格子被女孩擴展過，那麼直接返回現在的時間。
對於女孩，每次擴展一步，並標記擴展到的格子。
如果某個能擴展的格子被男孩擴展過，那麼直接返回現在的時間。
對於鬼，由於鬼是無視牆的，所以我們只需要在擴展男孩和女孩的時候，判斷下有沒有進入鬼的占領范圍即可。
題目中已經給出了，在第 k 秒後所有與鬼的曼哈頓距離不超過 2k 的位置都會被鬼占領
我們在第 t 秒擴展的時候，判斷被擴展的格子是否與某個鬼的曼哈頓距離小於 2t 即可
def check(x,y,step) : # 檢查該點能不能走到
if x<0 or x>=N or y<0 or y>=M : return False
if Map[x][y] == 'X' : return False
if abs(x-ghost[0][0]) + abs(y-ghost[0][1]) <= step * 2 : return False
if abs(x-ghost[1][0]) + abs(y-ghost[1][1]) <= step * 2 : return False
return True
def bfs() :
qM = [(Mi,Mj)] ; qG = [(Gi,Gj)]
st = [[0 for i in range(M)]for j in range(N)] # 記錄男生/女生走過的情況
st[Mi][Mj] = 1 ; st[Gi][Gj] = 2 # 記得把初始點放在st中
step = 0
while qM or qG : # 擴展男生
step += 1 # 時間+1
for n in range(3) : # 注意男生可以一次最多走三步
lenM = len(qM)
for _ in range(lenM) :
if qM == [] : break
nx,ny = qM.pop(0)
if not check(nx,ny,step) : continue
for i,j in [(1,0),(0,1),(-1,0),(0,-1)] :
px = nx + i ; py = ny + j
if not check(px,py,step) : continue
if st[px][py] == 2 : return step # 如果被女生走到過
if not st[px][py] : st[px][py] = 1 ; qM.append((px,py))
for n in range(1) :
lenG = len(qG) # 擴展女生
for _ in range(lenG) :
if qG == [] : break
nx,ny = qG.pop(0)
if not check(nx,ny,step) : continue
for i,j in [(1,0),(0,1),(-1,0),(0,-1)] :
px = nx + i ; py = ny + j
if not check(px,py,step) : continue
if st[px][py] == 1 : return step # 如果被男生走到過
if not st[px][py] : st[px][py] = 2 ; qG.append((px,py))
return -1
T = int(input())
for _ in range(T) :
N,M = map(int,input().split())
Map = []
for i in range(N) : Map.append(list(input()))
ghost = []
for i in range(N) :
for j in range(M) :
if Map[i][j] == 'M' : Mi,Mj = i,j
elif Map[i][j] == 'G' : Gi,Gj = i,j
elif Map[i][j] == 'Z' : ghost.append((i,j))
print(bfs())
