#3580. 噩梦 暂未评定

时间限制:1000 ms 内存限制:128 MiB 标准输入输出
题目类型:传统 评测方式:无测试数据
上传者: luffy

题目描述

给定一张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。

每个结果占一行。

样例

样例输入

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...

样例输出

1
1
-1

数据范围与提示

本题目版权归luffy所有

还记得我第一次看到这道题的时候刚进初一只觉得这道题非常非常非常 可是到了现在,我只会呵呵一笑:"原来就NM一个双向BFS!"

好了这道题该用什么思路做都很清楚了吧 我不会告诉你我还没搞数据