FZU 2150 Fire Game （暴力BFS）

网友投稿 301 2022-12-02

FZU 2150 Fire Game （暴力BFS）

【题目链接】​​click here~~​​

【题目大意】：

两个熊孩子要把一个正方形上的草都给烧掉，他俩同时放火烧，烧第一块的时候是不花时间的，每一块着火的都可以在下一秒烧向上下左右四块#代表草地，.代表着不能烧的。问你最少花多少时间可以烧掉，如果烧不掉就输出-1

【解题思路】：

数据比较弱的情况下直接暴力枚举每块草坪上可以放的位置，比较高端的写法目前没有想到，以后想到了文章更新下~~

ps:由于一个细节没注意，导致WA了几乎一页，还以为FZU 判题出错了，后来突然发现每次从队列里拿出队首的元素，才是和maxx比较时间的最大可能！

代码：

//FZU 2150#ifndef _GLIBCXX_NO_ASSERT#include #endif#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include // C++#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define rep(i,j,k) for(int i=(int)j;i<(int)k;++i)#define per(i,j,k) for(int i=(int)j;i>(int)k;--i)#define lowbit(a) a&-a#define Max(a,b) a>b?a:b#define Min(a,b) a>b?b:a#define mem(a,b) memset(a,b,sizeof(a))typedef long long LL;typedef unsigned long long LLU;typedef double db;const int N=105;const int inf=0x3f3f3f3f;int n,m,T;char mat[25][25];bool vis[N][N];int dir4[4][2]= {{1,0},{0,1},{-1,0},{0,-1}};int dir8[8][2]= {{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};int dir6[6][3]= {{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0}};///六个方向struct node{ int Coor_x; int Coor_y; int step;} q,p,mapp[N];bool ok(int dx,int dy){ if(dx>=0&&dx=0&&dy vall; vall.push(q); vall.push(p); while(!vall.empty()){ node q1,p1=vall.front(); vall.pop(); for(int i=0; i<4; ++i){ int dx=p1.Coor_x+dir4[i][0]; int dy=p1.Coor_y+dir4[i][1]; if(ok(dx,dy)&&!vis[dx][dy]&&mat[dx][dy]=='#'){ vis[dx][dy]=true; q1.Coor_x=dx; q1.Coor_y=dy; q1.step=p1.step+1; vall.push(q1); } } maxx=Max(maxx,p1.step);///大坑！，注意和vall.front() 比较 } return maxx;}int main(){ scanf("%d",&T); int tot=1; while(T--){ scanf("%d%d",&n,&m); getMat(); printf("Case %d: ",tot++); if(ans<=2){ puts("0"); continue; } int minn=inf; for(int i=0; i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：数据 输出
上一篇:#个人赛第六场解题总结#
下一篇:Java BufferedOutputStream类的常用方法讲解
相关文章

 发表评论

暂时没有评论，来抢沙发吧~