水灾 (BFS-先洪水后寻路)

水灾(sliker

大雨应经下了几天雨,却还是没有停的样子。ksy刚从外地回来,知道不久除了自己家,其他的地方都将会被洪水淹没。

ksy的老家可以用一个NM的地图表示,地图上有五种符号:“. X D S”。其中“X”表示石头,水和人都不能从上面经过。“.”表示平原,ksy和洪水都可以经过。“*”表示洪水开始地方(可能有多个地方开始发生洪水)。“D”表示ksy的家。“S”表示ksy现在的位置。

ksy每分钟可以向相邻位置移动,而洪水将会在ksy移动之后把相邻的没有的土地淹没(从已淹没的土地)。

求ksy回答家最少时间。如他回不了家,被淹死输出KAKTUS。

Input

3 3

D.*

.S.

Output

3

Input

3 3

D.*

..S

Output

KAKTUS

Input

3 6

D…*.

.X.X..

….S.

Output

6

因为第i秒走后,所到达的点不能有Flood

所以必须在之前Flood,然后再往下找

显然柯黑再同一个地方停留不优

故只要存储到达一个点的最短时间

注意C++中构造函数的写法

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<functional>
#include<algorithm>
#include<queue>
using namespace std;
#define MAXN (50+10)

struct node
{
    int x,y,t;
    node():x(0),y(0),t(0){}
    node(int _x,int _y,int _t):x(_x),y(_y),t(_t){/*cout<<x<<' '<<y<<' '<<t<<endl;*/}
}start,end;
/*
node made_node(int i,int j,int t)
{
    node now;
    now.x=i;
    now.y=j;
    now.t=t;
    return now;
}
*/

int n,m;
bool map[MAXN][MAXN],b[MAXN][MAXN];
char s[MAXN];   
queue<node> flood,q;
bool inside(int x,int y)
{
    if (x>=1&&x<=n&&y>=1&&y<=m) return true;
    return false;
}
bool bfs()
{
    int l=-1;
    while (!q.empty())
    {
        node now=q.front(); 
//      cout<<now.x<<' '<<now.y<<endl;
        q.pop();
        if (now.t>l)
        {
            int size=flood.size();
            while (size)
            {
                node nowf=flood.front();
                flood.pop();
                int x=nowf.x,y=nowf.y;              
                if (x>1&&b[x-1][y])
                {
                    flood.push(node(x-1,y,now.t));
                    map[x-1][y]=b[x-1][y]=0;
                }
                if (x<n&&b[x+1][y])
                {
                    flood.push(node(x+1,y,now.t));
                    map[x+1][y]=b[x+1][y]=0;
                }
                if (y>1&&b[x][y-1])
                {
                    flood.push(node(x,y-1,now.t));
                    map[x][y-1]=b[x][y-1]=0;
                }
                if (y<m&&b[x][y+1])
                {
                    flood.push(node(x,y+1,now.t));
                    map[x][y+1]=b[x][y+1]=0;
                }

                size--;
            }
            l++;
        }
        int x=now.x,y=now.y;
//      if (!map[x][y]) continue;
        if (x>1&&map[x-1][y])
        {
            if (x-1==end.x&&y==end.y){end.t=now.t+1; return true;}
            q.push(node(x-1,y,now.t+1));
            map[x-1][y]=0;
        }
        if (x<n&&map[x+1][y])
        {
            if (x+1==end.x&&y==end.y){end.t=now.t+1; return true;}
            q.push(node(x+1,y,now.t+1));
            map[x+1][y]=0;
        }
        if (y>1&&map[x][y-1])
        {
            if (x==end.x&&y-1==end.y){end.t=now.t+1; return true;}
            q.push(node(x,y-1,now.t+1));
            map[x][y-1]=0;
        }
        if (y<m&&map[x][y+1])
        {
            if (x==end.x&&y+1==end.y){end.t=now.t+1; return true;}
            q.push(node(x,y+1,now.t+1));
            map[x][y+1]=0;
        }

    }   
    return false;
}

int main()
{
    freopen("sliker.in","r",stdin);
    freopen("sliker.out","w",stdout);
    scanf("%d%d",&n,&m);
    memset(map,1,sizeof(map));
    memset(b,1,sizeof(b));      

    for (int i=1;i<=n;i++)
    {
        scanf("%s",s);
        for (int j=0;j<m;j++)
        {
            if (s[j]=='S')
            {
                start=node(i,j+1,0);
                q.push(start);
            }
            if (s[j]=='D') 
            {
                end=node(i,j+1,0);
                b[i][j+1]=0;
            }
            if (s[j]=='X') 
            {
                map[i][j+1]=0;
                b[i][j+1]=0;
            }
            if (s[j]=='*')
            {
                map[i][j+1]=0;
                b[i][j+1]=0;
                flood.push(node(i,j+1,0));
            }

        }
    }
/*  for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            if (map[i][j]) cout<<"map "<<i<<' '<<j<<endl;
    cout<<"end"<<end.x<<' '<<end.y;       
*/          

    if (bfs()) printf("%d\n",end.t);
    else printf("KAKTUS\n");

//  while (1);
    return 0;
}