题解 P4328 【[COCI2006-2007#1] Slikar】

昨日之日 · 2019-10-31 16:29:04 · 题解

这道题如果不考虑洪水的话，就是一道裸的bfs。

加了这个洪水之后只需要处理洪水到达每一个格子的最早时间，在广搜过程中如果遇到有现在的时间大于等于这个格子的洪水到达时间就直接扔掉。

需要注意的是在处理洪水的时候如果当前是避难所或者障碍物就不能加入队列。

另外一个坑点就是会有多个出洪水的点，所以洪水要先赋值成一个很大的值，再用min更新而不是直接赋值。

当时考试的时候没想仔细，其实这里也可以把所有出水点都加入队列，然后再搜索，这样时间复杂度会小很多。

#include<bits/stdc++.h>
using namespace std;
int n,m;
char a[55][55];
int fx[4][2]={1,0,0,1,-1,0,0,-1};
struct node {
    int x;
    int y;
    int cnt;//当前的时间
};
int water[55][55];
bool h_used[55][55];
queue <node> Water;
node startt,endd;
queue <node> Q;
node X[2505];
int xid;
void Water_Bfs(){
    while(!Water.empty()){
        node noww=Water.front();
        Water.pop();
        noww.cnt++;
        for(int i=0;i<4;i++){
            node _next=noww;
            _next.x+=fx[i][0],_next.y+=fx[i][1];
            if(_next.x<1||_next.y<1||_next.x>n||_next.y>m)continue;
            if(h_used[_next.x][_next.y])continue;
            water[_next.x][_next.y]=min(water[_next.x][_next.y],_next.cnt);
            Water.push(_next);
            h_used[_next.x][_next.y]=1;
        }
    }
}
void Ans_Bfs(){
    Q.push(startt);
    while(!Q.empty()){
        node noww=Q.front();
        Q.pop();
        if(water[noww.x][noww.y]<=noww.cnt)
            continue;
        if(noww.x==endd.x&&noww.y==endd.y){
            cout<<noww.cnt;
            return;
        }
        noww.cnt++;
        for(int i=0;i<4;i++){
            node _next=noww;
            _next.x+=fx[i][0],_next.y+=fx[i][1];
            if(_next.x<1||_next.y<1||_next.x>n||_next.y>m)continue;
            if(h_used[_next.x][_next.y])continue;
            if(a[_next.x][_next.y]=='X')continue;
            Q.push(_next);
            h_used[_next.x][_next.y]=1;
        }
    }
    cout<<"KAKTUS";
}
int main(){
    memset(water,127,sizeof(water));
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            cin>>a[i][j];
            if(a[i][j]=='S'){
                startt.x=i;
                startt.y=j;
                startt.cnt=0;
            }
            if(a[i][j]=='D'){
                endd.x=i;
                endd.y=j;
            }
            if(a[i][j]=='X'){
                X[xid].x=i;
                X[xid++].y=j;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]=='*'){
                node w;
                w.x=i;
                w.y=j;
                w.cnt=0;
                Water.push(w);
                water[i][j]=0;
                memset(h_used,0,sizeof(h_used));
                h_used[endd.x][endd.y]=1;
                for(int k=0;k<xid;k++){
                    h_used[X[k].x][X[k].y]=1;
                }
                Water_Bfs();
            }
        }
    }
    water[endd.x][endd.y]=1e8;
    memset(h_used,0,sizeof(h_used));
    h_used[startt.x][startt.y]=1;
    Ans_Bfs();
}