3489. [HDOJ 3085] 噩梦 Ⅱ

【题目描述】

昨晚，erriyue做了一个可怕的噩梦。他梦见他和他的女朋友被困在一个大迷宫里。更可怕的是，迷宫里有两个鬼魂。与他们相遇会被杀掉。现在erriyue想知道他是否能在鬼魂发现他们之前，找到他的女朋友。             

 你可以假设erriyue和他的女朋友可以向四个方向移动。每秒钟，erriyue能走3个单位距离，他的女朋友能走1个单位距离。鬼魂是邪恶的，每秒钟都会向四周分裂，每个鬼占据的区域每秒可以向四周扩张2个单位的距离，并且无视墙的阻挡，直到占据整个迷宫。也就是在k秒后所有的鬼的曼哈顿距离不超过2k的位置都会被鬼占领。

你可以假设，每一秒鬼魂首先分裂，然后erriyue和他的女朋友开始移动，求在不进入鬼魂占领区域的前提下，男孩和女孩能否会和，若能会和，求出最短会和时间。

【输入格式】

输入一个整数T，表示有T组数据。

 每组数据一行包含两个整数n和m，表示迷宫的大小。（1<n，m<800）

 接下来的n行描述了迷宫。每行包含m个字符。

字符可以是：

 “.”表示一个空旷的地方，所有人都可以在上面行走。

 “X”表示一堵墙，只有人不能在上面行走。

 “M”表示小erriyue

 “G”表示女朋友。

 “Z”表示鬼魂。

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

【输出格式】

输出T行

若可以相遇，则输出最短时间s,否则输出-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

【来源】

《算法竞赛进阶指南》HDOJ 3085