HDU3085 Nightmare Ⅱ

题意描述

给定一张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。
每个结果占一行。

解题思路

本题很显然是用bfs的解法，但是普通的bfs会超时，或者说普通的bfs很难处理这样几个人同时走动的题目。因此我们考虑用3个bfs同时进行，鬼先走2步，男孩再走3步，女孩再走1步，如果男孩和女孩在走动的过程中遇到对方，则说明在最短时间内相遇了。如果在一定步数内（取个大一点的数，10万吧）没相遇，说明肯定（基本上）不会再相遇了，那么我们就可以返回-1。
根据上述思路，很显然我们对每个角色的bfs是有限制的，即每秒钟每个人的步数有限，因此我们可以考虑用flag来记录每秒开始时该角色的初始步数，然后以此来限制本秒内步数只能小于flag+2（对于鬼）。

#include<cstdio>
#include<queue>
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});
        }
    }
    //最多走800*800步，因此循环1e5还没相遇即不可达 
    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;//男孩走3步 
        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;//女孩走1步 
        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;
}