FZU 2150 Fire Game （暴力BFS）

【题目链接】click here~~

【题目大意】：

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

【解题思路】：

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

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

代码：

#ifndef _GLIBCXX_NO_ASSERT

#include <cassert>

#endif

#include <cctype>

#include <cerrno>

#include <cfloat>

#include <ciso646>

#include <climits>

#include <clocale>

#include <cmath>

#include <csetjmp>

#include <csignal>

#include <cstdarg>

#include <cstddef>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

#include <algorithm>

#include <bitset>

#include <complex>

#include <deque>

#include <exception>

#include <fstream>

#include <functional>

#include <iomanip>

#include <ios>

#include <iosfwd>

#include <iostream>

#include <istream>

#include <iterator>

#include <limits>

#include <list>

#include <locale>

#include <map>

#include <memory>

#include <new>

#include <numeric>

#include <ostream>

#include <queue>

#include <set>

#include <sstream>

#include <stack>

#include <stdexcept>

#include <streambuf>

#include <string>

#include <typeinfo>

#include <utility>

#include <valarray>

#include <vector>

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<n&&dy>=0&&dy<m) return true;

return false;

}

int ans;

void getMat()

{

ans=0;

for(int i=0; i<n; ++i){

scanf("%s",mat[i]);

for(int j=0; j<m; ++j){

if(mat[i][j]=='#'){

ans++;

mapp[ans].Coor_x=i;

mapp[ans].Coor_y=j;

}

}

}

}

int bfs(int x1,int y1,int x2,int y2)

{

int maxx=0;

q.Coor_x=x1,q.Coor_y=y1,q.step=0;

p.Coor_x=x2,p.Coor_y=y2,p.step=0;

queue <node> 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);

}

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<ans; ++i){

for(int j=i; j<ans; ++j){

mem(vis,false);

vis[mapp[i].Coor_x][mapp[i].Coor_y]=true;

vis[mapp[j].Coor_x][mapp[j].Coor_y]=true;

bool flag=false;

int _minn=bfs(mapp[i].Coor_x,mapp[i].Coor_y,mapp[j].Coor_x,mapp[j].Coor_y);

for(int k=0; k<n; ++k){

for(int l=0; l<m; ++l){

if(mat[k][l]!='#') continue;

if(!vis[k][l]){

flag=true;

break;

}

}

}

if(!flag) minn=Min(_minn,minn);

}

}

if(minn==inf) puts("-1");

else printf("%dn",minn);

}

return 0;

}

相关知识

Couple Game下载
Game Framework 教程
使用BFS解决城镇路径问题
腐烂的橘子BFS算法解析
(转帖)生石花初级指南(扫盲贴——fire版)
红孩儿：决战火焰山Fire Ball: Journey to the West - The Secret Behind the Fiery Mountains (2005)
薄荷设计丨《人间草木》有故事的房子，花心思生活
【丁太升力挺周震南】PG:没有吴亦凡新说唱不成立；肖战被求婚？万圣节詹娜明日花晒照
闪百合花朵点缀婚订珠宝！小资新人也适合的Hearts On Fire Liliana轻奢风婚戒
一般图最大匹配：带花树入门详解

网址: FZU 2150 Fire Game （暴力BFS） https://www.huajiangbk.com/newsview1665994.html