FZU 2150 Fire Game(双起点)【BFS】

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

<题目链接>

题目大意：

两个熊孩子在n*m的平地上放火玩，#表示草，两个熊孩子分别选一个#格子点火，火可以向上向下向左向右在有草的格子蔓延，点火的地方时间为0，蔓延至下一格的时间依次加一。求烧完所有的草需要的最少时间。如不能烧完输出-1。

解题分析：

暴力枚举两个起点，然后用BFS求出这两个火源能够蔓延到最远的草地所花的时间，在那些能够烧完所有草地的情况中，选择用时最少的。

#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
#include <algorithm>typedef long long ll;
const int inf=0x3f3f3f3f;
using namespace std;char M[][],h[][];
int n,m,vis[][],res;
int next[][]={-,,,,,,,-};struct node
{
int x,y,step;
};
queue<node>q;
vector<node>v;bool judge() //判断是否所有的草全部烧过了
{
for(int i=;i<n;i++)
for(int j=;j<m;j++)
if(M[i][j]=='#'&&vis[i][j]==) return false;
return true;
}int bfs(node a,node b)
{
int num;
memset(vis,,sizeof(vis));
while(!q.empty()) q.pop();
q.push(a);vis[a.x][a.y]=;
q.push(b);vis[b.x][b.y]=;
while(!q.empty())
{
node now=q.front();q.pop();
num=now.step;
node nxt;
for(int i=;i<;i++){
nxt.x=now.x+next[i][];
nxt.y=now.y+next[i][];
nxt.step=now.step+;
if(nxt.x>=&&nxt.y>=&&nxt.x<n&&nxt.y<m&&M[nxt.x][nxt.y]=='#'&&!vis[nxt.x][nxt.y])
{
vis[nxt.x][nxt.y]=;
q.push(nxt);
}
}
}
return num; //num为能够烧到的所有点的最大步数
}int main()
{
int T,ncase=;cin>>T;
while(T--)
{
res=inf;
scanf("%d %d",&n,&m);
getchar();
v.clear();
for(int i=;i<n;i++){
scanf("%s",M[i]);
for(int j=;j<m;j++){
if(M[i][j]=='#'){
node a;a.x=i,a.y=j,a.step=;
v.push_back(a);
}
}
}
for(int i=;i<v.size();i++){
for(int j=i;j<v.size();j++){ //枚举两个起点
int tmp=min(bfs(v[i],v[j]),res);
if(judge())res=min(res,tmp);
}
}
printf("Case %d: ",++ncase);
if(res==inf) printf("-1\n");
else printf("%d\n",res);
}
}