P10487 Nightmare II

· · 个人记录

思路：

对于题目，其让我们判读男女在鬼魂的干扰下多久可以相遇

注意到这道题的困难在于

  1. erriyue 如何一次走三步
  2. 如何判断鬼魂

对于第一个问题其实很好解决，将两人的BFS队列分开处理，erriyue 走三步则每次进行三次扩散

这样就等于他在同样的时间里走了三步

而对于问题二判断鬼魂则我们可以使用曼哈顿距离求解：当时间为 time 时我们需要判断此时到达的点与鬼的曼哈顿距离是否大于时间的两倍，为什么是曼哈顿距离且要大于时间的两倍呢？

因为鬼魂没法斜着走，所以是曼哈顿距离而不是欧几里得距离，大于两倍是因为鬼魂每秒都走两步

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn(1e4+10);
struct node{
    int x,y;
    bool flag;
};
int n,m,T;
int tim(0);
vector<node>op;
queue<node>Q1,Q2;
char mp[maxn][maxn];
bool vis[maxn][maxn][2];
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
inline void csh(){    //初始化
    tim=0;
    memset(vis,false,sizeof(vis));
    while(Q1.size()){
        Q1.pop();
    }
    while(Q2.size()){
        Q2.pop();
    }
    op.clear();
}
int dis(node a,node b){   //曼哈顿距离
    return abs(a.x-b.x)+abs(a.y-b.y);
}
bool check(node a){   //对于普通墙壁
    if(a.x<1||a.y<1||a.x>n||a.y>m||mp[a.x][a.y]=='X'||vis[a.x][a.y][a.flag]){
        return false;
    }
    return true;
}
bool check2(node x){    //对于鬼魂
    for(int i(0);i<2;i++){
        if(dis(x,op[i])<=tim*2){
            return false;
        }
    }
    return true;
}
int BFS(){
    while(Q1.size()&&Q2.size()){
        tim++;
        int number(3);
        while(number--){   //男人走，重复三遍==走三步
            int len(Q1.size());
            while(len--){
                node now(Q1.front());
                Q1.pop();
                if(!check2(now)){
                    continue;
                }
                for(int i(0);i<4;i++){
                    int nx(now.x+dx[i]);
                    int ny(now.y+dy[i]);
                    if(!(check({nx,ny,now.flag}))||(!check2({nx,ny,1}))){
                        continue;
                    }
                    vis[nx][ny][now.flag]=true;
                    if(vis[nx][ny][!now.flag]){
                        return tim;
                    }
                    Q1.push({nx,ny,now.flag});
                }
            }
        }
        int len(Q2.size());
        while(len--){  //女人走
            node now(Q2.front());
            Q2.pop();
            if(!check2(now)){
                continue;
            }
            for(int i(0);i<4;i++){
                int nx(now.x+dx[i]);
                int ny(now.y+dy[i]);
                if(!(check({nx,ny,now.flag}))||(!check2({nx,ny,1}))){
                    continue;
                }
                vis[nx][ny][now.flag]=true;
                if(vis[nx][ny][!now.flag]){
                    return tim;
                }
                Q2.push({nx,ny,now.flag});
            }
        }
    }
    return -1;
}
int main(){
    cin>>T;
    while(T--){
        csh();
        cin>>n>>m;
        for(int i(1);i<=n;i++){
            for(int j(1);j<=m;j++){
                cin>>mp[i][j];
                if(mp[i][j]=='M'){
                    Q1.push({i,j,true});
                    vis[i][j][1]=true;
                }
                if(mp[i][j]=='G'){
                    Q2.push({i,j,false});
                    vis[i][j][0]=true;
                }
                if(mp[i][j]=='Z'){
                    op.push_back({i,j,true});
                }
            }
        }
        cout<<BFS()<<'\n';
    }
    return 0;
}