题目描述

给定一张N*M的地图，地图中有1个男孩，1个女孩和2个鬼。
字符“.”表示道路，字符“X”表示墙，字符“M”表示男孩的位置，字符“G”表示女孩的位置，字符“Z”表示鬼的位置。
男孩每秒可以移动3个单位距离，女孩每秒可以移动1个单位距离，男孩和女孩只能朝上下左右四个方向移动。
每个鬼占据的区域每秒可以向四周扩张2个单位距离，并且无视墙的阻挡，也就是在第k秒后所有与鬼的曼哈顿距离不超过2k的位置都会被鬼占领。
注意： 每一秒鬼会先扩展，扩展完毕后男孩和女孩才可以移动。
求在不进入鬼的占领区的前提下，男孩和女孩能否会合，若能会合，求出最短会合时间。

样例

输入样例：
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

C++ 代码

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int r,c,t; 
};
int dr[] = {0,1,0,-1};
int dc[] = {1,0,-1,0};
const int N = 1000;
char G[N][N];
int t,n,m;

int solve(){
    queue<Node> boy,girl,ghost;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            if(G[i][j] == 'M') boy.push(Node{i,j,0});
            else if(G[i][j] == 'G') girl.push(Node{i,j,0});
            else if(G[i][j] == 'Z') ghost.push(Node{i,j,0});
        }
    }
    for(int i = 0;i <= 100000;i++){
        int flag = ghost.front().t;
        while(ghost.size() && ghost.front().t < flag+2){
            Node x = ghost.front();ghost.pop();
            for(int j = 0;j < 4;j++){
                int r = x.r + dr[j];
                int c = x.c + dc[j];
                if(G[r][c] != '#'){
                    ghost.push(Node{r,c,x.t+1});
                    G[x.r][x.c] = G[r][c] = '#';
                } 
            }
        }
        flag = boy.front().t;
        while(boy.size() && boy.front().t < flag+3){
            Node x = boy.front();boy.pop();
            if(G[x.r][x.c] != 'M') continue;
            for(int j = 0;j < 4;j++){
                int r = x.r + dr[j];
                int c = x.c + dc[j];
                if(G[r][c] == '.') boy.push(Node{r,c,x.t+1}),G[x.r][x.c] = 'X',G[r][c] = 'M';
                else if(G[r][c] == 'G') return i+1;
            }
        }
        flag = girl.front().t; 
        while(girl.size() && girl.front().t < flag+1){
            Node x = girl.front();girl.pop();
            if(G[x.r][x.c] != 'G') continue;
            for(int j = 0;j < 4;j++){
                int r = x.r + dr[j];
                int c = x.c + dc[j];
                if(G[r][c] == '.') girl.push(Node{r,c,x.t+1}),G[x.r][x.c] = 'X',G[r][c] = 'G';
                else if(G[r][c] == 'M') return i+1;
            }
        }
    }
    return -1; 
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(int i = 1;i <= n;i++) scanf("%s",G[i]+1); 
        for(int i = 0;i <= n+1;i++) 
            G[i][0] = G[i][m+1] = '#';
        for(int i = 0;i <= m+1;i++) 
            G[0][i] = G[n+1][i] = '#';
        printf("%d\n",solve());
    }
    return 0;
}