欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Nightmare Ⅱ HDU - 3085

程序员文章站 2022-12-02 23:48:20
HDU - 3085读题太难了,请看这位大神的翻译:大神的中文题意思路:这就是一道暴力BFS模拟啊!!最多再加点A*作为佐料暴力跑就完事儿,最多算一下在当前点会不会被鬼抓到作为剪枝在这里我安利一下一篇优秀的题解:大神的题解嗯?我为什么要在自己的题解里安利别人的题解?因为我的题解是给自个儿看的嗷代码附:#pragma GCC optimize("Ofast","inline","-ffast-math")#pragma GCC target("avx,sse2,sse3,sse4,mmx")...

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