[kuangbin带你飞]专题一 简单搜索 I

题目:[kuangbin带你飞]专题一 简单搜索 I

思路：看题目就是一题bfs题目，和传统题目不通在于：

• 开始的点是两个点，而且有多种不同的状态，需要枚举取最小时间。
• 不是去搜索一个点，而是去搜索所有连通的地方算得到最短时间。

如何判断搜索是否完成？

• 判断该点为#，且未访问过，那么就没有搜索完成。

if(mm[i][j]=='#'&&!vis[i][j])

我的代码：

#include<iostream>
#include<cstring>
#include<queue>
#define MaxN  0x3f3f3f3f
using namespace std;
int R,C; 
int mov[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
bool vis[110][110];
char mm[110][110];
struct node {
    int x;
    int y;
    int time;
};

bool check(node nownode){
    if(nownode.x<0||nownode.y<0||nownode.x>=R||nownode.y>=C||vis[nownode.x][nownode.y]||mm[nownode.x][nownode.y]!='#')
        return false;
    return true;
}


int bfs(node st1,node st2){
    queue<node> Q;
    Q.push(st1);
    Q.push(st2);
    vis[st1.x][st1.y] = true;
    vis[st2.x][st2.y] = true;
    node nownode;
    node nextnode;
    while(!Q.empty()){
        nownode = Q.front();Q.pop();
        for(int i =0 ;i<4;i++){
            nextnode.x = nownode.x+mov[i][0];
            nextnode.y = nownode.y+mov[i][1];
            if(check(nextnode)){
                vis[nextnode.x][nextnode.y] = true;
                nextnode.time = nownode.time + 1;
                Q.push(nextnode);
            }
        }
    }
    return nownode.time;
}

bool test(){
    for(int i = 0;i<R;i++){
        for(int j =0;j<C;j++){
            if(mm[i][j]=='#'&&!vis[i][j]) return false;
        }
    }
    return true;
}

int enumerate(){
    node st1;
    node st2;
    int mintime=MaxN;
    int thistime=MaxN;
    st1.time = 0;
    st2.time = 0;
    for(int i = 0;i<R;i++){
        for(int j =0 ;j<C;j++){
            if(mm[i][j] == '#'){
                st1.x = i;
                st1.y = j;
                for(int z =0;z<R;z++){
                    for(int s=0;s<C;s++){
                        if(mm[z][s]=='#'){
                            st2.x = z;
                            st2.y = s;
                            memset(vis,false,sizeof(vis));
                            thistime = bfs(st1,st2);
                            //如果没烧完，时间不算 
                            if(!test()) continue;
                            if(thistime<mintime){
                                mintime=thistime;
                            }
                        }
                    }
                }
            }
            
        }
    }
    return mintime;
}

void init(){
        cin>>R>>C;
        for(int i =0;i<R;i++){
            for(int j = 0 ;j<C;j++){
                cin>>mm[i][j];
            }
        }
}



int main(){
    int T;
    int ccase=0;
    cin>>T;
    while(T--){
        init();
        int mintime;
        mintime = enumerate();
        if(mintime==MaxN){
            cout<<"Case "<<++ccase<<": -1"<<endl;
        }else{
            cout<<"Case "<<++ccase<<": "<<mintime<<endl;
        }
    }
}