Nightmare 噩梦

题目描述:

给定一张n*m的地图，地图中有1个男孩、1个女孩和2个鬼。字符“.“表示道路，字符”X“表示墙，字符”M" 表示男孩的位置，字符“G"表示女孩的位置，字符”Z"表示鬼的位置。 男孩每秒可以在道路上移动3个单位距离，女孩每秒可以在道路上移到1个单位距离。 每个鬼占据的区域每秒可以向四周扩张2个单位距离，并且无视墙的阻挡， 也就是说在第K秒后所有与鬼的曼哈顿距离不超过2K 的位置都会被鬼占领。

每一秒都是鬼先扩张，然后男孩女孩再走。

求在不进入鬼的占领区的前提下， 男孩与女孩能否会合，若能会合，求出最短会合时间。

输入格式:

第一行包含两个整数 n 和 m， 表示地图的大小。 (1<n, m<800)

接下来n行，描述地图。每行包含m个字符，这些字符的含义如下：
‘.’ 表示空地，所有人可以通过；
‘X’ 表示墙，人不能通过；
‘M’ 男孩所在的位置；
‘G’ 女孩所在的位置；
‘Z’ 鬼所在的位置；

所有数据均保证只有一个M、一个G、两个Z。

输出格式:

仅包含一个整数S，表示男孩和女孩相遇的最短时间，如果不能会合输出-1。

样例输入:

样例1;
5 6
XXXXXX
XZ..ZX
XXXXXX
M.G...
......

样例2：
5 6
XXXXXX
XZZ..X
XXXXXX
M.....
..G...

样例3：
10 10
..........
..X.......
..M.X...X.
X.........
.X..X.X.X.
.........X
..XX....X.
X....G...X
...ZX.X...
...Z..X..X

样例输出:

样例1：
1

样例2：
1

样例3：
-1

提示:

1<= N, M <=800

时间限制: 1000ms
空间限制: 256MB

---