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

输入样例：

35 6XXXXXXXZ..ZXXXXXXX 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

输出样例：

11-1

 

算法：bfs

题解：就是先枚举鬼能走到的位置，然后在枚举女孩和男孩要走到的位置，重复做这件事，直到女孩能碰到男孩，否则输出-1.因为它走过的次数不会超过1e5次（读者可以自己证明）。

 

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int maxn = 1e3+7;struct node {    int x, y, step;};char Map[maxn][maxn];int dir[4][2] = {
   0, -1, 0, 1, -1, 0, 1, 0};int n, m;bool check(int x, int y) {    if(x <= 0 || x > n || y <= 0 || y > m) {        return false;    }    return true;}int bfs() {    queue
        
          girl, boy, ghost;    for(int i = 1; i <= n; i++) {        for(int j = 1; j <= m; j++) {            if(Map[i][j] == 'M') {                boy.push((node){i, j, 0});            } else if(Map[i][j] == 'G') {                girl.push((node){i, j, 0});            } else if(Map[i][j] == 'Z') {                ghost.push((node){i, j, 0});            }        }    }    for(int i = 1; i <= 100005; i++) {      //枚举来遍历这些时间        int tmp = ghost.front().step + 2;   //限制了移动的距离        while(!ghost.empty() && ghost.front().step < tmp) {             node now = ghost.front();            ghost.pop();            for(int j = 0; j < 4; j++) {                int tx = now.x + dir[j][0];                int ty = now.y + dir[j][1];                if(check(tx, ty) && Map[tx][ty] != '#') {                    ghost.push((node){tx, ty, now.step + 1});                    Map[tx][ty] = '#';                    Map[now.x][now.y] = '#';                }            }        }        tmp = boy.front().step + 3;        while(!boy.empty() && boy.front().step < tmp) {            node now = boy.front();            boy.pop();            for(int j = 0; j < 4; j++) {                int tx = now.x + dir[j][0];                int ty = now.y + dir[j][1];                if(check(tx, ty) && Map[tx][ty] != '#') {                    if(Map[tx][ty] == '.') {                        boy.push((node){tx, ty, now.step + 1});                        Map[tx][ty] = 'M';                        Map[now.x][now.y] = 'X';                    } else if(Map[tx][ty] == 'G') {                        return i;                    }                }            }        }        tmp = girl.front().step + 1;        while(!girl.empty() && girl.front().step < tmp) {            node now = girl.front();            girl.pop();            for(int j = 0; j < 4; j++) {                int tx = now.x + dir[j][0];                int ty = now.y + dir[j][1];                if(check(tx, ty) && Map[tx][ty] != '#') {                    if(Map[tx][ty] == '.') {                        girl.push((node){tx, ty, now.step + 1});                        Map[tx][ty] = 'G';                        Map[now.x][now.y] = 'X';                    } else if(Map[tx][ty] == 'M') {                        return i;                    }                }            }        }               }    return -1;}int main() {    int T;    scanf("%d", &T);    while(T--) {        scanf("%d %d", &n, &m);        for(int i = 1; i <= n; i++) {            getchar();            for(int j = 1; j <= m; j++) {                scanf("%c", &Map[i][j]);            }        }        printf("%d\n", bfs());    }    return 0;}