题意:在 n*m 的图中'#'表示草坪'.'表示空地,可以选择在任意的两个草坪格子点火,火每 1 s 会向周围四个格子扩散,问选择那两个点使得燃烧完所有的草坪花费时间最小。
分析:广度搜索,点火的格子可以为同一个。双循环遍历可以点火的草地,搜索得到每次烧完所用的步数,记录最小的一个。搜索是为了记录烧过的草地,和每次最外层草地烧完花费的时间。
代码:
- 1#include 2#include 3#include 4#include 5#include 6#include 7#include 8#include < set > 9#include 10#include 11 using namespace std;
- 12#define ll long long 13#define inf 0x3f3f3f3f 14 char g[15][15];
- 15 bool vis[15][15];
- 16 int to[4][2] = {
- 0,
- 1,
- 0,
- -1,
- 1,
- 0,
- -1,
- 0
- };
- 17 int n,
- m;
- 18 struct node 19 {
- 20 int x,
- y,
- t;
- 21
- };
- 22 vector v;
- 23 int bfs(node a, node b) 24 {
- 25 int i,
- j,
- s;
- 26 memset(vis, 0, sizeof vis);
- 27 queue q;
- 28 a.t = b.t = 0;
- 29 vis[a.x][a.y] = vis[b.x][b.y] = 1;
- 30 q.push(a);
- q.push(b);
- 31
- while (!q.empty()) 32 {
- 33 a = q.front();
- 34 q.pop();
- 35 s = a.t;
- 36
- for (i = 0; i < 4; i++) 37 {
- 38 b.x = a.x + to[i][0];
- 39 b.y = a.y + to[i][1];
- 40
- if (b.x >= 0 && b.x = 0 && b.y '#') 41 {
- 42 vis[b.x][b.y] = 1;
- 43 b.t = a.t + 1;
- 44 q.push(b);
- 45
- }
- 46
- }
- 47
- }
- 48
- return s; //最后一个能烧到的草地所花时间
- 49
- }
- 50 int main() 51 {
- 52 int i,
- j,
- k,
- l,
- t;
- 53 scanf("%d", &t);
- 54
- for (l = 1; l <= t; l++) 55 {
- 56 scanf("%d %d", &n, &m);
- 57 v.clear();
- 58
- for (i = 0; i) 59 {
- 60 getchar();
- 61
- for (j = 0; j) 62 {
- 63 scanf("%c", &g[i][j]);
- 64
- if (g[i][j] == '#') 65 v.push_back((node) {
- i,
- j,
- 0
- }); //是草地则作为备选初始节点加入向量
- 66
- }
- 67
- }
- 68 int mi = inf;
- 69
- for (i = 0; i) 70
- for (j = i; j) 71 {
- 72 int tmp = bfs(v[i], v[j]); //选两个初始点搜索
- 73 bool ok = 1;
- 74
- for (k = 0; k //判断是否烧完所有草地
- 75 {
- 76
- if (!vis[v[k].x][v[k].y]) 77 {
- 78 ok = 0;
- break;
- 79
- }
- 80
- }
- 81
- if (ok) mi = min(mi, tmp); 82
- }
- 83 printf("Case %d: ", l);
- 84
- if (mi == inf) puts("-1");
- 85
- else printf("%d\n", mi);
- 86
- }
- 87
- return 0;
- 88
- }
来源: http://www.cnblogs.com/Nautilus1s/p/6014393.html