Top

FZU - 2150 - Fire Game(双端BFS)


题目链接

题意:

给你块地,有空地,也有草堆,让你选两个草堆进行点火,燃烧的草堆会引燃上下左右的相邻草堆,
每一次引燃花费1s时间,问你最少花多长时间把草堆都点着,如果做不到输出-1.

题解:

枚举图中所有草地,找到任意两块不一样的草地,然后bfs求出烧掉所有草的最短时间,
可以将两个初始状态都push进队列,这样就可以模拟两堆草同时燃烧的情况,
在bfs的过程中要判断是否烧完(即所有的草堆的点都要被访问过),如果烧完,就立即返回这点的距离,
就是以该状态枚举时,的最远距离,让后输出最远距离中最小的就是最终结果。

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn = 20;
struct node{
int x, y;
node(int i = 0, int j = 0){ x = i, y = j; };
};
char mp[maxn][maxn];
int vis[maxn][maxn];
int n, m;
int _size;
int dis[4][2] = { 1, 0, -1, 0, 0, 1, 0, -1 };
vector<node>cp;
int bfs(node a, node b){
memset(vis, 0, sizeof(vis));
queue<node>dq;
dq.push(a);
dq.push(b);
vis[a.x][a.y] = vis[b.x][b.y] = 1;
int ans = 1; //能达到的最大时间
node na, nb;
while (!dq.empty()){
a = dq.front(), dq.pop();
for (int i = 0; i<4; i++){
na.x = a.x + dis[i][0];
na.y = a.y + dis[i][1];
if (na.x >= 0 && na.x<n&&na.y >= 0 && na.y<m&&mp[na.x][na.y] == '#'&&vis[na.x][na.y] == 0)
dq.push(na), vis[na.x][na.y] = vis[a.x][a.y] + 1, ans = max(ans, vis[na.x][na.y]);
}
}

for (int i = 0; i<_size; i++){ //遍历所有草堆看看是否全部都已经被火覆盖
if (vis[cp[i].x][cp[i].y] == 0)return -1;
}
return ans;
}
int main(){
int t, tt = 1;
scanf("%d", &t);
node xx;
while (tt <= t){
cp.clear();
scanf("%d%d", &n, &m);
for (int i = 0; i<n; i++){
getchar();
for (int j = 0; j<m; j++){
scanf("%c", &mp[i][j]);
xx.x=i,xx.y=j;
if (mp[i][j] == '#')cp.push_back(xx); //存入#节点坐标,便于枚举火堆
}
}

int ans = 99999999;
_size = cp.size();
if(_size==1)ans=1;
//for(int i=0;i<_size;i++)cout<<cp[i].x<<" "<<cp[i].y<<endl;
for (int i = 0; i<_size; i++){
for (int j = i + 1; j<_size; j++){
int tmp = bfs(cp[i], cp[j]); //枚举火堆跑bfs
if(tmp==-1)continue;
ans=min(tmp,ans);
}
}
if(ans==99999999)printf("Case %d: -1\n", tt++);
else printf("Case %d: %d\n", tt++, ans-1);
}
return 0;
}
文章版权为Anoyer博客所有,转载请以链接形式标明本文地址