FZU 2150 Fire Game 广度优先搜索,暴力 难度:0

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

注意这道题可以任选两个点作为起点,但是时间仍足以穷举两个点的所有可能

#include <cstdio>

#include <cstring>

#include <queue>

using namespace std;

const int maxn=11;

const int inf=0x3fffffff;

char maz[maxn][maxn];

int dp[maxn][maxn];

int n,m,mxn,num;

queue<int> que;

const int dx[8]={0,0,1,-1,1,1,-1,-1};

const int dy[8]={1,-1,0,0,1,-1,1,-1};

struct pnt {

        int x,y;

        pnt(){x=y=0;}

        pnt(int tx,int ty){x=tx,y=ty;}

};

bool in(int x,int y){

        return x>=0&&x<n&&y>=0&&y<m;

}

void bfs(pnt s,pnt s2){

        while(!que.empty())que.pop();

        int tnum=0;

        int tmxn=0;

        dp[s.x][s.y]=0;

        tnum++;

        que.push(s.x*maxn+s.y);

        if(s2.x!=s.x||s2.y!=s.y){

                dp[s2.x][s2.y]=0;

                tnum++;

                que.push(s2.x*maxn+s2.y);

        }

        while(!que.empty()){

                int x=que.front()/maxn,y=que.front()%maxn;que.pop();

                tmxn=max(tmxn,dp[x][y]);

                for(int i=0;i<4;i++){

                        int tx=x+dx[i],ty=y+dy[i];

                        if(in(tx,ty)&&maz[tx][ty]=='#'&&dp[tx][ty]>dp[x][y]+1){

                                dp[tx][ty]=dp[x][y]+1;

                                tnum++;

                                que.push(tx*maxn+ty);

                        }

                }

        }

        if(tnum==num)mxn=min(mxn,tmxn);

}

void init(){

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

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

                        dp[i][j]=inf;

                }

        }

}

pnt heap[maxn*maxn];int hlen;

int main(){

        int T;

        scanf("%d",&T);

        for(int ti=1;scanf("%d%d",&n,&m)==2&&ti<=T;ti++){

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

                        scanf("%s",maz[i]);

                }

                num=0;mxn=inf;hlen=0;

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

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

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

                                        num++;

                                        heap[hlen++]=pnt(i,j);

                                }

                        }

                }

                for(int i=0;i<hlen;i++){

                        for(int j=i;j<hlen;j++){

                                init();

                                bfs(heap[i],heap[j]);

                        }

                }

                printf("Case %d: %d\n",ti,mxn==inf?-1:mxn);

        }

        return 0;

}