题目描述

小明做了一个可怕的噩梦，梦见他和他 的朋友分别被困在一个大迷宫里。更可怕的是，在迷宫里有两个魔鬼， 他们会杀人。小明想知道他能否在魔鬼找到他们之前找到他的朋友。小 明和他的朋友可以朝四个方向移动。在每秒内，小明都可以移动3步， 他的朋友可以移动1步。魔鬼每秒都会分裂成几部分，占据两步之内的 网格，直到占据整个迷宫。假设魔鬼每秒都会先分裂，然后小明和他的 朋友开始移动，如果小明或他的朋友到达一个有魔鬼的格子，就会死 （新的魔鬼也可以像原来的魔鬼一样分裂）。

输入格式

输入以整数$T$开头，表示测试用例的数量。每个测试用例 的第1行都包含两个整数$n$ 和$m$（$1<n ,m <800$），表示迷宫的行数和列 数。接下来的$n$ 行，每行都包含$m$ 个字符，字符

“.”表示一个空地方，所有人都可以走；

“X”表示一堵墙，只有人不能走；

“M”表示小明；

“G”表示小明的朋友；

“Z”表示魔鬼，

保证包含一个字母$M$、一 个字母$G$和两个字母$Z$。

输出格式

如果小明和他的朋友能够见面，则单行输出见面的最短时 间，否则输出-1。

样例

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

来源

HDU3085