Fire Game--FZU2150（bfs）

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

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=65959#problem/I

题意： 从两个任意点点着草地 火会向上下左右四个方向蔓延

         相邻的草地就会被点着

         问最短多长时间点燃所有草地

思路：其实就是枚举两个点同时进队列进行bfs

        其中要注意 草地小于等于二时 要特殊处理

#include<iostream>
#include<stdio.h>
#include<string.h>
#define INF 0xfffffff
#include<queue>
#include<algorithm>
using namespace std;
#define N 15

int vis[N][N],n,m,counts,mark[N][N][N][N],Mark,sum;
int dir[4][2]={ {1,0},{-1,0},{0,-1},{0,1} };
char maps[N][N];

struct node
{
    int x,y,step;
};

void bfs(node s1,node s2)
{
    queue<node>Q;
    node p,q;
    s1.step=s2.step=0;
    sum=0;
    memset(vis,0,sizeof(vis));
    Q.push(s1);
    Q.push(s2);
    vis[s1.x][s1.y]=vis[s2.x][s2.y]=1;
    while(!Q.empty())
    {
        q=Q.front();
        Q.pop();
        for(int i=0;i<4;i++)
        {
            p.x=q.x+dir[i][0];
            p.y=q.y+dir[i][1];
            if(p.x<n&&p.x>=0&&p.y>=0&&p.y<m&&vis[p.x][p.y]==0&&maps[p.x][p.y]=='#')
            {
                p.step=q.step+1;
                vis[p.x][p.y]=1;
                Q.push(p);
                Mark++;// 已经燃烧的地方个数；
            }
        }
        sum=max(sum,q.step);
    }
}

int main()
{
    int T,i,j,ans,t=0;
    node s1,s2;
    scanf("%d",&T);
    while(T--)
    {
        t++;
        memset(mark,0,sizeof(mark));
        scanf("%d%d",&n,&m);
        counts=sum=0;
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
            {
                cin>>maps[i][j];
                if(maps[i][j]=='#')
                    counts++;
            }
        }
        printf("Case %d: ",t);
        if(counts<=2)//如果只有两块一下的草地，为0；
        {
            printf("0
");continue;
        }
        ans=INF;
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
            {
                if(maps[i][j]=='#')//第一个点为‘#’；
                {
                    for(int ii=0;ii<n;ii++)
                    {
                        for(int jj=0;jj<m;jj++)
                        {
                            if(maps[ii][jj]=='#'&&(ii!=i||jj!=j)&&mark[i][j][ii][jj]==0)//要满足两点不同并且没有被同时当做起点；
                            {
                                mark[ii][jj][i][j]=mark[i][j][ii][jj]=1;//标记说明这两个点被当过起点；
                                s1.x=i,s1.y=j;
                                s2.x=ii,s2.y=jj;
                                s1.step=s2.step=0;
                                Mark=2;//刚开始的两个起点被烧过了；
                                bfs(s1,s2);
                                if(ans>sum&&Mark==counts/*看是否把所有草地都燃烧完了；*/)
                                    ans=sum;
                            }
                        }
                    }
                }
            }
        }
        if(ans==INF)
            printf("-1
");
        else
            printf("%d
",ans);
    }
    return 0;
}