#88. 噩梦

噩梦

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一张N×M\red{N\times M}的地图,地图中有1\red{1}个男孩,1\red{1}个女孩和2\red{2}个鬼。

字符“.\red{.}”表示道路,字符“X\red{X}”表示墙,字符“M\red{M}”表示男孩的位置,字符“G\red{G}”表示女孩的位置,字符“Z\red{Z}”表示鬼的位置。

男孩每秒可以移动3\red{3}个单位距离,女孩每秒可以移动1\red{1}个单位距离,男孩和女孩只能朝上下左右四个方向移动。

每个鬼占据的区域每秒可以向四周扩张2\red{2}个单位距离,并且无视墙的阻挡,也就是在第k\red{k}秒后所有与鬼的曼哈顿距离不超过2k\red{2k}的位置都会被鬼占领。

输入格式

第一行包含整数T\red{T},表示共有T\red{T}组测试用例。

每组测试用例第一行包含两个整数N\red{N}M\red{M},表示地图的尺寸。

接下来N\red{N}行每行M\red{M}个字符,用来描绘整张地图的状况。(注意:地图中一定有且仅有1\red{1}个男孩,1\red{1}个女孩和2\red{2}个鬼)

输出格式

每个测试用例输出一个整数S\red{S},表示最短会合时间。

如果无法会合则输出1\red{-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

提示

数据范围:1<n,m<800

注意: 每一秒鬼会先扩展,扩展完毕后男孩和女孩才可以移动。

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

周日下午线上班2(周日下午讲解题目)

未参加
状态
已结束
规则
ACM/ICPC
题目
5
开始于
2021-9-21 17:00
结束于
2021-9-30 1:00
持续时间
200 小时
主持人
参赛人数
3