首页 > > 程序设计 > C/C++ >

kuangbin专题专题一简单搜索 Fire Game FZU - …

2019-08-16 07:48:12来源：博客园阅读 ()

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 }