Nightmare Ⅱ HDU - 3085

HDU - 3085
读题太难了，请看这位大神的翻译：大神的中文题意

思路：
这就是一道暴力BFS模拟啊！！最多再加点A*作为佐料
暴力跑就完事儿，最多算一下在当前点会不会被鬼抓到作为剪枝
在这里我安利一下一篇优秀的题解：大神的题解

嗯？我为什么要在自己的题解里安利别人的题解？因为我的题解是给自个儿看的嗷

代码附：

#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define pf push_front
using namespace std;
const int N = 2e5+10;
int n,m,turn;
char mp[888][888];
struct node
{
    int x,y;
} boy,girl,ghost[2];
int X[5]= {1,-1,0,0};
int Y[5]= {0,0,1,-1};
queue<node>M,G;
bool check(node k)
{
    for(int i=0; i<2; ++i)
        if(turn*2>=abs(k.x-ghost[i].x)+abs(k.y-ghost[i].y)||k.x<0||k.x>=n||k.y<0||k.y>=m||mp[k.x][k.y]=='X')
            return true;
    return false;
}
bool BFS(bool sex,int steps,char c)
{
    queue<node>save;
    for(int done=1; done<=steps; ++done)
    {
        if(sex)
            save=M;
        else
            save=G;
        while(save.size())
        {
            node k=save.front();
            save.pop();
            if(sex)
                M.pop();
            else
                G.pop();
            if(check(k))
                continue;
            for(int i=0; i<4; ++i)
            {
                node kk=k;
                kk.x+=X[i];
                kk.y+=Y[i];
                if(check(kk)||mp[kk.x][kk.y]==c)
                    continue;
                if(mp[kk.x][kk.y]=='G'||mp[kk.x][kk.y]=='M')
                    return true;
                mp[kk.x][kk.y]=c;
                if(sex)
                    M.push(kk);
                else
                    G.push(kk);
            }
        }
    }
    return false;
}
int work()
{
    while(M.size())
        M.pop();
    while(G.size())
        G.pop();
    for(int i=0,cnt=0; i<n; ++i)
    {
        for(int j=0; j<m; ++j)
        {
            if(mp[i][j]=='M')
                boy.x=i,boy.y=j;
            else if(mp[i][j]=='G')
                girl.x=i,girl.y=j;
            else if(mp[i][j]=='Z')
                ghost[cnt].x=i,ghost[cnt].y=j,cnt=1;
        }
    }
    M.push(boy);
    G.push(girl);
    turn=0;
    while(M.size()&&G.size())
    {
        turn++;
        if(BFS(1,3,'M')||BFS(0,1,'G'))
            return turn ;
    }
    return -1;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        for(int i=0; i<n; ++i)
            cin>>mp[i];
        cout<<work()<<endl;
    }
    return 0;
}

本文地址：https://blog.csdn.net/qq_43586463/article/details/107395023