设为首页 加入收藏

TOP

kuangbin专题 专题一 简单搜索 Fire Game FZU - 2150
2019-07-10 16:11:20 】 浏览:15
Tags:kuangbin 专题 简单 搜索 Fire Game FZU 2150

 

题目链接:https://vjudge.net/problem/FZU-2150

题意:’ . '代表火无法烧着的地方,‘ # ’表示草,火可以烧着。选择任意两个‘ # ’(可以两个都选同一个 ‘ # ’),火会蔓延,每过1个时间消耗,向四周蔓延。问:能不能把草全部烧完,可以的话得出最短时间,否则输出 -1。

思路:bfs,枚举所有点火情况就OK了,直接看代码吧。


 

  1 #include <iostream>
  2 #include <cstring>
  3 #include<vector>
  4 #include<string>
  5 #include <cmath>
  6 #include <map>
  7 #include <queue>
  8 #include <algorithm>
  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<node> 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" << endl; 134 cout << "Case " << o << ": " << (ans == inf ? -1 : ans) << endl; 135 } 136 137 return 0; 138 }

 

 




编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇gcc5+opencv4.0.1 玄学bug记录 下一篇kuangbin专题 专题一 简单搜索 Pr..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(217) }