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
上一篇: 网管必备!平息环路造成的广播风暴
推荐阅读
-
HDU 2256Problem of Precision(矩阵快速幂)
-
湫湫系列故事——设计风景线 HDU - 4514
-
HDU6315 Naive Operations(线段树 复杂度分析)
-
【题解】hdu1506 Largest Rectangle in a Histogram
-
C - Monkey and Banana HDU 1069( 动态规划+叠放长方体)
-
HDU 1052(田忌赛马 贪心)
-
hdu-1338 game predictions(贪心题)
-
致初学者(四):HDU 2044~2050 递推专项习题解
-
C语言BFS--Find a way(Hdu 2612)
-
『ACM C++』HDU杭电OJ | 1425 - sort (排序函数的特殊应用)