FZU2150 fire 雙搜bfs

題目連結：http://acm.fzu.edu.cn/problem.php?pid=2150

題意：在任意兩處點火，求最短時間燒光所有草堆。

規模：1 <= T <=100, 1 <= n <=10, 1 <= m <=10

類型：暴力+雙搜

分析：題目很好了解，枚舉兩個起點進行雙搜就好。但以前沒有敲過雙搜，中間出了不少狀況，wa了很多發，主要問題是在“如何使兩個queue完成目前時間下的搜尋”。

時間複雜度&&優化：

代碼：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<algorithm>
#include<iostream>

using namespace std;

const int MAX_N = ;
const int MAX_M = ;
const int inf = ;
const int mod = ;

int n,m;
int a[][];
int b[][];

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

int dx[]={,,,-};
int dy[]={,-,,};

bool judge(int x,int y){
    if(x>=&&x<n&&y>=&&y<m&&b[x][y]==){
            b[x][y]=;
        //cout<<"!"<<endl;
        return true;
    }
    return false;
}

int bfs(int ax,int ay,int bx,int by){
    int res=;
    for(int i=;i<n;i++){
        for(int j=;j<m;j++){
            b[i][j]=a[i][j];
        }
    }
    b[ax][ay]=;
    b[bx][by]=;
    queue<point>q,p;
    while(!q.empty()){q.pop();}
    while(!p.empty()){p.pop();}
    point st1,st2;
    st1.x=ax;st1.y=ay;st1.step=;
    st2.x=bx;st2.y=by;st2.step=;
    q.push(st1);p.push(st2);
    int stp=;
    point tmp,tmp2;
    while(!q.empty() || !p.empty()){
        if(!q.empty()){
            int key_step=q.front().step;
            while(!q.empty()&&q.front().step==key_step){
                tmp=q.front();
                //cout<<tmp.x<<" "<<tmp.y<<" "<<tmp.step<<endl;
                q.pop();
                stp=tmp.step;
                res=max(res,stp);
                for(int i=;i<;i++){
                    tmp2.x=tmp.x+dx[i];
                    tmp2.y=tmp.y+dy[i];
                    tmp2.step=tmp.step+;
                    if(judge(tmp2.x,tmp2.y))q.push(tmp2);
                }
//                if(ax==1&&ay==1&&bx==7&&by==2){
//                    cout<<stp<<" "<<tmp.x<<" "<<tmp.y<<endl;
//                }
            }

        }

        if(!p.empty()){
            int key_step=p.front().step;
            while(!p.empty()&&p.front().step==key_step){
                tmp=p.front();
                p.pop();
                stp=tmp.step;
                res=max(res,stp);
                for(int i=;i<;i++){
                    tmp2.x=tmp.x+dx[i];
                    tmp2.y=tmp.y+dy[i];
                    tmp2.step=tmp.step+;
                    if(judge(tmp2.x,tmp2.y))p.push(tmp2);
                }
//                if(ax==1&&ay==1&&bx==7&&by==2){
//                    cout<<stp<<" "<<tmp.x<<" "<<tmp.y<<endl;
//                }
            }

        }

    }
    for(int i=;i<n;i++){
        for(int j=;j<m;j++){
            if(b[i][j]==)return -;
        }
    }
//    //cout<<stp<<" "<<ax<<" "<<ay<<"   "<<bx<<" "<<by<<endl;
//    if(stp==3)cout<<3<<" "<<ax<<" "<<ay<<"   "<<bx<<" "<<by<<endl;
//    if(stp==4)cout<<4<<" "<<ax<<" "<<ay<<"   "<<bx<<" "<<by<<endl;
    return res;
}

int solve(){
    int res=inf;
    for(int i=;i<n*m;i++){
        if(a[i/m][i%m]==)

        for(int j=i+;j<n*m;j++){
            if(a[j/m][j%m]==){
               // cout<<i<<" "<<j<<endl;
                int k=bfs(i/m,i%m,j/m,j%m);
                if(k!=-)res=min(res,k);
            }
        }
    }
    if(res==inf)return -;
    else return res;
}

int main()
{
    //freopen("test.txt","r",stdin);
    int T;char c;
    cin>>T;
    for(int z=;z<=T;z++){
        memset(a,,sizeof(a));
        cin>>n>>m;
        int tot=;
        for(int i=;i<n;i++){
            for(int j=;j<m;j++){
                cin>>c;
                if(c=='#'){a[i][j]=;tot++;}
                else a[i][j]=;
            }
        }
        if(tot<=){printf("Case %d: %d\n",z,);}
        else printf("Case %d: %d\n",z,solve());
    }

    return ;
}