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

· · 题解

这道题不难，乍一看数据很小：(R,C<=50) 您可以使用DFS或BFS

基本流程：

我们并不需要每走一步就模拟扩散一次洪水，首先这样可能有点麻烦，其次时间复杂度较大。

显而易见，洪水的扩散是不会受刺猬走动影响的

用一个BFS（好像也只能是BFS，当然如果有人用DFS写出来也没必要惊讶）来进行模拟水到每个点的流动的最小时间(预处理)

然后跑一个(DFS/BFS),走到每个点，用当前步行的时间比较当前位置水流到这里的最快时间，只要是大于等于的，就不能继续跑图，否则就能够继续跑图。

最后：

特判:

至于障碍嘛，其实有没有障碍都是一样的，只不过你跑不到那，水也不能流到那……

参考程序:（程序出处:crh1272336175的题解）

#include<bits/stdc++.h>
using namespace std;
const int M=55;
int n,m,sx,sy,ex,ey,ans=0x3f3f3f3f;
char str[M][M];
int t[M][M],visited[M][M];//t用于记录洪水到达某个点的时间 
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};//上下左右 
struct flood
{
    int x,y,t;//坐标和洪水到达的时间 
    flood(const int &x,const int &y, const int &t):x(x),y(y),t(t){}
};
queue<flood> qriver,q;
void bfs_water()
{
    while(!qriver.empty())
    {
        flood now=qriver.front(); qriver.pop();
        for(int i=0; i<4; i++)
        {
            int nx=now.x+dx[i],ny=now.y+dy[i];
            if(nx>=1 && nx<=n && ny>=1 && ny<=m)//判断边界
                if(str[nx][ny]=='.' && !visited[nx][ny])//能走得通且没访问过'
                {
                    visited[nx][ny]=1;
                    if(t[nx][ny]>now.t+1) t[nx][ny]=now.t+1;
                    qriver.push(flood{nx,ny,now.t+1});
                }   
        }
    }
}
void bfs_person()
{
    memset(visited,0,sizeof visited);
    q.push(flood{sx,sy,0});
    while(!q.empty())
    {
        flood now=q.front(); q.pop();
        for(int i=0; i<4; i++)
        {
            int nx=now.x+dx[i],ny=now.y+dy[i];
            if(nx==ex && ny==ey)
                ans=min(ans,now.t+1); 
            if(nx>=1 && nx<=n && ny>=1 && ny<=m)//判断边界
                if(str[nx][ny]=='.' && t[nx][ny]>now.t+1&& !visited[nx][ny])//能走得通且没访问过
                {
                    visited[nx][ny]=1;
                    if(t[nx][ny]>now.t+1) t[nx][ny]=now.t+1;
                    q.push(flood{nx,ny,now.t+1});
                }   
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
    {
        scanf("%s",str[i]+1);
        for(int j=1; j<=m; j++)
        {
            char c=str[i][j];
            if(c=='S') sx=i,sy=j;
            else if(c=='D') ex=i,ey=j;
            else if(c=='*') qriver.push(flood{i,j,0});
        }
    }
    memset(t,0x3f3f3f3f,sizeof t);
    bfs_water();
    bfs_person();
    if(ans==0x3f3f3f3f) puts("KAKTUS");
    else printf("%d\n",ans);
    return 0;
}