FZU-2150.FireGame.(BFS))

　　本题大意：给出一个n * m的地，‘#’ 代表草， ‘.’代表陆地，每次选择这片地里的两片草，可选相等的草，选择的两片草初始状态为被燃状态，每一分钟被点燃的草会将身边的四连块点。问你需要对于给定的这片地最少需要多少分钟能燃烧完，燃烧不完输出 -1.

　　本题思路：很直观的一道题，枚举所有可能开始燃烧的点，更新最小值就行，无法燃烧完则是输出-1。

　　参考代码：

 //要勤于思考，思考使人明智，不要总是因为一两个点没有想到就浪费时间

 #include <cstdio>

 #include <queue>

 #include <cmath>

 #include <cstring>

 #include <vector>

 using namespace std;

 struct node {

     int x, y, step;

 }now, Next;

 const int maxn =  + , INF = 0x3f3f3f3f;

 int n, m, t, ans, connected_block, maxstep, Case = ;

 char maze[maxn][maxn];

 bool vis_index[maxn][maxn];

 vector <node> grass;

 bool check () {

     for(int i = ; i < n; i ++)

         for(int j = ; j < m; j ++)

             if(maze[i][j] == '#' && !vis_index[i][j]) return false;

     return true;

 }

 bool useful(int x, int y) {

     return (x >=  && y >=  && x < n && y < m && maze[x][y] == '#' && !vis_index[x][y]);

 }

 void Init() {

     grass.clear();

     memset(vis_index, false, sizeof vis_index);

     ans = INF, connected_block = ;

 }

 int bfs(node n1, node n2) {

     queue < node> Q;

     memset(vis_index, false, sizeof vis_index);

     Q.push(n1), Q.push(n2);

     maxstep = ;

     while(!Q.empty()) {

         now = Q.front();

         Q.pop();

         if(vis_index[now.x][now.y]) continue;

         maxstep = now.step;

         vis_index[now.x][now.y] = true;

         for(int dx = -; dx <= ; dx ++) {

             for(int dy = -; dy <= ; dy ++) {

                 if(abs(dx - dy) == ) {

                     if(useful(now.x + dx, now.y + dy)) {

                         Next.x = now.x + dx, Next.y = now.y + dy, Next.step = now.step + ;

                         Q.push(Next);

                     }

                 }

             }

         }

     }

     return maxstep;

 }

 int main () {

     scanf("%d", &t);

     while(t --) {

         Init();

         scanf("%d %d", &n, &m);

         getchar();

         for(int i = ; i < n; i ++) {

             for(int j = ; j < m; j ++) {

                 maze[i][j] =getchar();

                 if(maze[i][j] == '#') {

                     node g;

                     g.x = i, g.y = j, g.step = ;

                     grass.push_back(g);

                 }

             }

             getchar();

         }

         //Find answer

         for(int i = ; i < grass.size(); i ++)

             for(int j = i; j < grass.size(); j ++) {

                 grass[i].step = , grass[j].step = ;

                 int temp = min(bfs(grass[i], grass[j]), ans);

                 if(check()) ans = min(temp, ans);

             }

         printf("Case %d: ", ++ Case);

         if(ans == INF) printf("-1\n");

         else printf("%d\n", ans);

     }

     return ;

 }