No testdata at current.

题目描述

给定一张 $N\times N$ 的地图，地图中有 $1$ 个男孩，$1$ 个女孩和 $2$ 个鬼。

字符 . 表示道路，字符 X 表示墙，字符 M 表示男孩的位置，字符 G 表示女孩的位置，字符 Z 表示鬼的位置。

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

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

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

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

输入有点玄学，需要用快读输入测试数据组数 $T$：

inline int read() {
	int x = 0, f = 1; char s = getchar();
	while (s < '0' || s > '9') { if (s == '-') f = -f; s = getchar(); }
	while (s >= '0' && s <= '9') { x = x * 10 + s - '0'; s = getchar(); }
	return x * f;
}

int main() {
    int T = read();	// 在主函数中
    // ...
}

如果不用快读可以来原题这里提交

输入格式

第一行包含整数 $T$，表示共有 $T$ 组测试用例。

每组测试用例第一行包含两个整数 $N$ 和 $M+$，表示地图的尺寸。

接下来 $N$ 行每行 $M$ 个字符，用来描绘整张地图的状况。

注意：地图中一定有且仅有 $1$ 个男孩，$1$ 个女孩和 $2$ 个鬼。

输出格式

每个测试用例输出一个整数 $S$，表示最短会合时间。

如果无法会合则输出 -1。

每个结果占一行。

样例

样例输入

1
5 6
XXXXXX
XZZ..X
XXXXXX
M.....
..G...

样例输出

1

数据范围与提示

对于 $100\%$ 的数据，有$1<n,m<800$ 。