题意：’ . '代表火无法烧着的地方，‘ # ’表示草，火可以烧着。选择任意两个‘ # ’（可以两个都选同一个 ‘ # ’），火会蔓延，每过1个时间消耗，向四周蔓延。问：能不能把草全部烧完，可以的话得出最短时间，否则输出 -1。
思路：bfs，枚举所有点火情况就OK了，直接看代码吧。
1 #include 2 #include 3 #include 4 #include<string> 5 #include 6 #include 7 #include 8 #include 9 using namespace std; 10 11 #define inf (1LL <<31) - 1 12 #define rep(i,j,k) for(int i = (j); i <= (k); i++) 13 #define rep__(i,j,k) for(int i = (j); i <(k); i++) 14 #define per(i,j,k) for(int i = (j); i >= (k); i--) 15 #define per__(i,j,k) for(int i = (j); i > (k); i--) 16 17 const int N = 20; 18 int mv_x[4] = { 0, 0, 1, -1 }; 19 int mv_y[4] = { 1, -1, 0, 0 }; 20 int x[120]; //草的x 21 int y[120]; //草的y 22 int l; //几颗草 23 char mp[N][N]; //原始地图 24 char cp_mp[N][N]; //原始地图副本，用于bfs 25 bool vis[N][N]; 26 int ans; //答案 27 int n, m; 28 29 struct node{ 30 int x, y, c; 31 node(){} 32 node(int o, int oo, int ooo){ 33 x = o; 34 y = oo; 35 c = ooo; 36 } 37 }; 38 39 inline void input(){ 40 41 l = 0; 42 rep(i, 1, n) rep(j, 1, m){ 43 cin >> mp[i][j]; 44 45 //记录下所有草 46 if (mp[i][j] == '#'){ 47 x[l] = i; 48 y[l++] = j; 49 } 50 } 51 } 52 53 //每种情况前，初始化函数 54 inline void init_vis_And_cp_mp(){ 55 memset(vis, 0, sizeof(vis)); 56 memcpy(cp_mp, mp, sizeof(mp)); 57 } 58 59 //边界 60 inline bool check(int x, int y){ 61 return x >= 1 && x <= n && y >= 1 && y <= m; 62 } 63 64 //检查草是否都烧完 65 bool all_Fired(){ 66 rep(i, 1, n) rep(j, 1, m){ 67 if (cp_mp[i][j] == '#' && !vis[i][j]) return false; 68 } 69 70 return true; 71 } 72 73 void bfs(int x1, int y1, int x2, int y2){ 74 75 queue que; 76 77 //标记两个点火源 78 vis[x1][y1] = true; 79 vis[x2][y2] = true; 80 81 //放入队列 82 node a1(x1, y1, 0); 83 node a2(x2, y2, 0); 84 que.push(a1); 85 que.push(a2); 86 87 int tmp_ans = 0; 88 while (!que.empty()){ 89 90 node tmp = que.front(); 91 que.pop(); 92 93 tmp_ans = max(tmp_ans, tmp.c); //这里是得出能烧到的草的最后时间 94 95 rep__(p, 0, 4){ 96 97 int dx = tmp.x + mv_x[p]; 98 int dy = tmp.y + mv_y[p]; 99 100 //没越界，没被访问过，是草 101 if (check(dx, dy) && !vis[dx][dy] && cp_mp[dx][dy] == '#'){ 102 vis[dx][dy] = true; 103 node k(dx, dy, tmp.c + 1); 104 que.push(k); 105 } 106 } 107 } 108 109 //全部烧完才能算一个答案 110 if (all_Fired()) ans = min(ans, tmp_ans); 111 } 112 113 int main(){ 114 115 ios::sync_with_stdio(false); 116 cin.tie(0); 117 118 int T; 119 cin >> T; 120 121 rep(o, 1, T){ 122 123 cin >> n >> m; 124 input(); 125 126 ans = inf; // 127 128 //枚举点火情况 129 rep__(i, 0, l ) rep__(j, i, l){ 130 init_vis_And_cp_mp(); //每种情况前，初始化函数 131 bfs(x[i], y[i], x[j], y[j]); //两个点火源 132 } 133 // cout <<"Case 1: 1" < 134 cout <<"Case " <": " <<(ans == inf ? -1 : ans) << endl; 135 } 136 137 return 0; 138 }
京公网安备 11010802041100号