题目链接：http://acm.fzu.edu.cn/problem.php?pid=2150

 

题目大意：

有一张n×m的地图，地图上 ‘#’ 表示草地，’.’ 表示空地，一哥们可以选择至多两个草地点燃（非法操作，请小伙伴们不要模仿），火势会蔓延到这个草地的四周的草地，且需要一个单位的时间，问能否把这个地图上的草地都点燃，如果可以输出需要的最小时间，如果不行输出-1。

 

思路：

先用一个点BFS去初始化‘#’点，用一个数组去记录到达‘#’的最短时间。然后再用第二个点去BFS就可以了。具体的还是看代码吧。

 

  1 #include <iostream>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <queue>
  5 #include <stdlib.h>
  6 
  7 #define inf 0x3f3f3f3f
  8 using namespace std;
  9 const int maxn = 15;
 10 
 11 typedef struct Node{
 12     int x;
 13     int y;
 14     int cnt;
 15 }Node;
 16 
 17 
 18 queue<Node> q; //这里注意只用一个队列，如果用两个的话会TL
 19 int T;
 20 int ant;
 21 int M_ans = inf;
 22 int n,m;
 23 char map[maxn][maxn];
 24 int mx[] = {0,0,1,-1};
 25 int my[] = {1,-1,0,0};
 26 int step[maxn][maxn],vis[maxn][maxn];
 27 
 28 
 29 int get_ans()
 30 {
 31     int ans = 0;
 32     for (int i=0;i<n;i++)
 33     {
 34         for (int j=0;j<m;j++)
 35         {
 36             if (map[i][j] == '#')
 37             {
 38                 ans = max(ans,step[i][j]);
 39             }
 40         }
 41     }
 42     M_ans = min(M_ans,ans);
 43 }
 44 
 45 
 46 void init_bfs(int a,int b)
 47 {
 48     memset(vis,0, sizeof(vis));
 49     memset(step,inf, sizeof(step));
 50     Node node;
 51     node.x = a;
 52     node.y = b;
 53     node.cnt = 0;
 54     q.push(node);
 55     while (!q.empty())
 56     {
 57         Node w = q.front();
 58         q.pop();
 59         if (step[w.x][w.y] > w.cnt)
 60             step[w.x][w.y] = w.cnt;
 61         for (int k=0;k<4;k++)
 62         {
 63             Node e = w;
 64             int nx = e.x + mx[k];
 65             int ny = e.y + my[k];
 66             if (map[nx][ny] == '#' && nx>=0 && ny>=0 && nx<n && ny<m && step[nx][ny] == inf)
 67             {
 68                 e.x = nx;
 69                 e.y = ny;
 70                 e.cnt++;
 71                 step[nx][ny] = e.cnt;
 72                 q.push(e);
 73             }
 74         }
 75     }
 76 }
 77 
 78 void bfs(int i,int j)
 79 {
 80     Node node;
 81     node.x = i;
 82     node.y = j;
 83     node.cnt = 0;
 84     q.push(node);
 85     vis[i][j] = 1;
 86     q.push(node);
 87     while (!q.empty())
 88     {
 89         Node cur = q.front();
 90         q.pop();
 91         if (step[cur.x][cur.y] > cur.cnt)
 92             step[cur.x][cur.y] = cur.cnt;
 93         for (int k=0;k<4;k++)
 94         {
 95             Node next = cur;
 96             int nx = next.x + mx[k];
 97             int ny = next.y + my[k];
 98             if (map[nx][ny] == '#' && nx>=0 && ny>=0 && nx<n && ny<m && !vis[nx][ny] && step[nx][ny]>next.cnt+1)
 99             {
100                 next.cnt++;
101                 step[nx][ny] = next.cnt;
102                 next.x = nx;
103                 next.y = ny;
104                 vis[nx][ny] = 1;
105                 q.push(next);
106             }
107         }
108     }
109 
110 }
111 
112 
113 
114 int main()
115 {
116     ios_base::sync_with_stdio(0);
117     cin.tie(NULL);
118     cin >> T;
119     int t = 1;
120     while (T--)
121     {
122         ant = 0;
123         M_ans = inf;
124         cin >> n >> m;
125         for (int i=0;i<n;i++)
126         {
127             for (int j=0;j<m;j++)
128             {
129                 cin >> map[i][j];
130             }
131         }
132         for (int i=0;i<n;i++)
133         {
134             for (int j=0;j<m;j++)
135             {
136                 for (int i1=0;i1<n;i1++)
137                 {
138                     for (int j1=0;j1<m;j1++)
139                     {
140                         if (map[i][j]=='#' && map[i1][j1] == '#' )
141                         {
142                             init_bfs(i,j);
143                             bfs(i1,j1);
144                             get_ans();
145                         }
146                     }
147                 }
148             }
149         }
150         if (M_ans == inf)
151             printf("Case %d: -1\n",t++);
152         else
153             printf("Case %d: %d\n",t++,M_ans);
154     }
155     return 0;
156 }