#88. 噩梦
噩梦
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
给定一张的地图,地图中有个男孩,个女孩和个鬼。
字符“”表示道路,字符“”表示墙,字符“”表示男孩的位置,字符“”表示女孩的位置,字符“”表示鬼的位置。
男孩每秒可以移动个单位距离,女孩每秒可以移动个单位距离,男孩和女孩只能朝上下左右四个方向移动。
每个鬼占据的区域每秒可以向四周扩张个单位距离,并且无视墙的阻挡,也就是在第秒后所有与鬼的曼哈顿距离不超过的位置都会被鬼占领。
输入格式
第一行包含整数,表示共有组测试用例。
每组测试用例第一行包含两个整数和,表示地图的尺寸。
接下来行每行个字符,用来描绘整张地图的状况。(注意:地图中一定有且仅有个男孩,个女孩和个鬼)
输出格式
每个测试用例输出一个整数,表示最短会合时间。
如果无法会合则输出。
每个结果占一行。
输入样例
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
注意: 每一秒鬼会先扩展,扩展完毕后男孩和女孩才可以移动。
求在不进入鬼的占领区的前提下,男孩和女孩能否会合,若能会合,求出最短会合时间。