hdu3329（2次dfs）

传送门：The Flood

题意：当水的高度升为多少的时候，能够将这块区域分为两个部分.

分析：枚举高度，先从外围开始一次dfs，将水能淹没的标记，然后看非标记的是否已分为多块。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define inf 0x7fffffff

#define LL long long

#define N 110

using namespace std;

inline LL read()

{

    LL x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

int n,m;

int a[N][N];

bool vis[N][N];

void dfs2(int x,int y)

{

    vis[x][y]=true;

    for(int i=-;i<=;i++)

        for(int j=-;j<=;j++)

        {

            int ax=x+i,by=y+j;

            if(ax>n||ax<||by>m||by<||i+j==||i==j)continue;

            if(!vis[ax][by])dfs2(ax,by);

        }

}

void dfs(int x,int y)

{

    vis[x][y]=true;

    for(int i=-;i<=;i++)

        for(int j=-;j<=;j++)

        {

            int ax=x+i,by=y+j;

            if(ax>n+||ax<||by>m+||by<||i+j==||i==j)continue;

            if(!vis[ax][by]&&!a[ax][by])dfs(ax,by);

        }

}

int judge()

{

    memset(vis,false,sizeof(vis));

    dfs(,);

    int res=;

    for(int i=;i<=n;i++)

        for(int j=;j<=m;j++)

        {

            if(!vis[i][j]&&a[i][j])dfs2(i,j),res++;

        }

    return res>;

}

void solve()

{

    int ans=,flag=;

    for(int i=;flag;i++,ans++)

    {

        if(judge())

        {

            printf("Island splits when ocean rises %d feet.\n",ans);

            return;

        }

        flag=;

        for(int i=;i<=n;i++)

        for(int j=;j<=m;j++)

        {

            if(a[i][j])a[i][j]--,flag=;

        }

    }

    puts("Island never splits.");

}

int main()

{

    int cas=;

    while(scanf("%d%d",&n,&m)>)

    {

        if(n+m==)break;

        memset(a,,sizeof(a));

        for(int i=;i<=n;i++)

        {

            for(int j=;j<=m;j++)

                scanf("%d",&a[i][j]);

        }

        printf("Case %d: ",cas++);

        solve();

    }

}