给定一张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。
每个结果占一行。
数据范围
1<n,m<8001<n,m<800
输入样例：
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
算法：bfs
题解：就是先枚举鬼能走到的位置，然后在枚举女孩和男孩要走到的位置，重复做这件事，直到女孩能碰到男孩，否则输出-1.因为它走过的次数不会超过1e5次（读者可以自己证明）。
#include <iostream>
#include <cstdio>
#include <queue> using namespace std; const int maxn = 1e3+; struct node {
int x, y, step;
}; char Map[maxn][maxn];
int dir[][] = {, -, , , -, , , };
int n, m; bool check(int x, int y) {
if(x <= || x > n || y <= || y > m) {
return false;
}
return true;
} int bfs() {
queue<node> girl, boy, ghost;
for(int i = ; i <= n; i++) {
for(int j = ; j <= m; j++) {
if(Map[i][j] == 'M') {
boy.push((node){i, j, });
} else if(Map[i][j] == 'G') {
girl.push((node){i, j, });
} else if(Map[i][j] == 'Z') {
ghost.push((node){i, j, });
}
}
}
for(int i = ; i <= ; i++) { //枚举来遍历这些时间
int tmp = ghost.front().step + ; //限制了移动的距离
while(!ghost.empty() && ghost.front().step < tmp) {
node now = ghost.front();
ghost.pop();
for(int j = ; j < ; j++) {
int tx = now.x + dir[j][];
int ty = now.y + dir[j][];
if(check(tx, ty) && Map[tx][ty] != '#') {
ghost.push((node){tx, ty, now.step + });
Map[tx][ty] = '#';
Map[now.x][now.y] = '#';
}
}
}
tmp = boy.front().step + ;
while(!boy.empty() && boy.front().step < tmp) {
node now = boy.front();
boy.pop();
for(int j = ; j < ; j++) {
int tx = now.x + dir[j][];
int ty = now.y + dir[j][];
if(check(tx, ty) && Map[tx][ty] != '#') {
if(Map[tx][ty] == '.') {
boy.push((node){tx, ty, now.step + });
Map[tx][ty] = 'M';
Map[now.x][now.y] = 'X';
} else if(Map[tx][ty] == 'G') {
return i;
}
}
}
}
tmp = girl.front().step + ;
while(!girl.empty() && girl.front().step < tmp) {
node now = girl.front();
girl.pop();
for(int j = ; j < ; j++) {
int tx = now.x + dir[j][];
int ty = now.y + dir[j][];
if(check(tx, ty) && Map[tx][ty] != '#') {
if(Map[tx][ty] == '.') {
girl.push((node){tx, ty, now.step + });
Map[tx][ty] = 'G';
Map[now.x][now.y] = 'X';
} else if(Map[tx][ty] == 'M') {
return i;
}
}
}
} }
return -;
} int main() {
int T;
scanf("%d", &T);
while(T--) {
scanf("%d %d", &n, &m);
for(int i = ; i <= n; i++) {
getchar();
for(int j = ; j <= m; j++) {
scanf("%c", &Map[i][j]);
}
}
printf("%d\n", bfs());
}
return ;
}