学步园

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

题意：一个平面上有n堆草，两个人想在上面OOXX，所以要把草烧光（我也不知道为什么，题目这么说的），一个人只能烧一堆草，草烧着的话一个单位时间后会烧着它周围的草，当然如果它周围有草的话，如果草堆大于2个他们就不能烧完输出-1，输出至少要多长时间他们能把草烧完。注意两个人可以同时烧同一堆草。

拿到这题首先想到了森林火灾，是个bfs，我首先用dfs判断了一下草堆的个数，然后最长要多少时间，我鬼使神差的想成了dfs，dfs最长深度就是至少需要的时间，果断WA了，因为和深度无关，和横纵坐标差值有关，然后我又判断了一下横纵坐标差，继续WA，这下不知道错在哪了。又把题看了一遍，发现：两个人可以同时烧一堆草。。。。

不想重新写了，想来想去，dfs的确做不了，bfs也有特点，它是从两个点一起搜的，然后我把每个草堆的点存在了新的结构体数组中，枚举两两个点，结构体中记录时间，找最长的时间，然后再判断一下地图中草是否全部烧光，因为有可能两堆草枚举了同一堆的两个点，这样使得另一堆草没有烧，答案必然也不对，就没必要更新答案了。如果草都烧光了就更新答案。

不想多说了，漏看条件WA了一下午

#include<cstring>
#include<string>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#include<functional>
#include<cmath>
using namespace std;
#define PI acos(-1.0)
#define MAXN 810
#define eps 1e-7
#define INF 0x7FFFFFFF
typedef long long ll;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

struct node{
    int x,y,step;
}mp[110];
queue<node> q;
int n, m, cnt;
int ans1;
char a[15][15];
int vis[15][15];
int dir[4][2] = {1,0,-1,0,0,1,0,-1};
bool cango(int x,int y){
    if(x<n&&x>=0&&y<m&&y>=0)    return true;
    return false;
}
void dfs(int x,int y){
    vis[x][y] = 1;
    int i, j;
    for(i=0;i<4;i++){
        int xx = x + dir[i][0];
        int yy = y + dir[i][1];
        if(cango(xx,yy)&&a[xx][yy]=='#'&&!vis[xx][yy]){
            dfs(xx,yy);
        }
    }
}
int main(){
    int t, i, j, k = 1, cntk, flag;
    scanf("%d",&t);
    while(t--){
        while(!q.empty())   q.pop();
        cntk = 0;
        memset(vis,0,sizeof(vis));
        ans1 = 110;
        scanf("%d%d",&n,&m);
        for(i=0;i<n;i++){
            scanf("%s",a[i]);
            for(j=0;j<m;j++){
                if(a[i][j]=='#'){
                    mp[cntk].x = i;
                    mp[cntk].y = j;
                    cntk++;
                }
            }
        }
        cnt = 0;
        for(i=0;i<n;i++){
            for(j=0;j<m;j++){
                if(a[i][j]=='#'&&!vis[i][j]){
                    dfs(i,j);
                    cnt++;
                }
            }
        }
        if(cnt>2){
            printf("Case %d: -1\n",k++);
            continue;
        }
        int cnt1;
        for(i=0;i<cntk;i++){
            for(j=i;j<cntk;j++){
                //cout<<mp[i].x<<mp[i].y<<endl;
                cnt1 = 0;
                flag = 0;
                memset(vis,0,sizeof(vis));
                vis[mp[i].x][mp[i].y] = 1;
                vis[mp[j].x][mp[j].y] = 1;
                mp[i].step = 0;
                mp[j].step = 0;
                q.push(mp[i]);
                q.push(mp[j]);
                while(!q.empty()){
                    //cout<<"aaaaaaaaaaa"<<endl;
                    node tt = q.front();
                    q.pop();
                    int ii;
                    for(ii=0;ii<4;ii++){
                        int ttx = tt.x + dir[ii][0];
                        int tty = tt.y + dir[ii][1];
                        if(cango(ttx,tty)&&a[ttx][tty]=='#'&&!vis[ttx][tty]){
                            vis[ttx][tty] = 1;
                            node temp;
                            temp.x = ttx;
                            temp.y = tty;
                            temp.step = tt.step+1;
                            q.push(temp);
                        }
                    }
                    if(tt.step>cnt1) cnt1 = tt.step;
                }
                for(int ii=0;ii<n;ii++){
                    for(int jj=0;jj<m;jj++){
                        if(a[ii][jj]=='#')
                            if(!vis[ii][jj]){
                                flag = 1;
                                break;
                        }
                    }
                    if(flag)    break;
                }
                if(flag)    continue;
                if(cnt1<ans1)    ans1 = cnt1;
            }
        }
        printf("Case %d: %d\n",k++,(ans1==110)?-1:ans1);
    }
    return 0;
}