传送门：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=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';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=-1;i<=1;i++) for(int j=-1;j<=1;j++) { int ax=x+i,by=y+j; if(ax>n||ax<1||by>m||by<1||i+j==0||i==j)continue; if(!vis[ax][by])dfs2(ax,by); } } void dfs(int x,int y) { vis[x][y]=true; for(int i=-1;i<=1;i++) for(int j=-1;j<=1;j++) { int ax=x+i,by=y+j; if(ax>n+1||ax<0||by>m+1||by<0||i+j==0||i==j)continue; if(!vis[ax][by]&&!a[ax][by])dfs(ax,by); } } int judge() { memset(vis,false,sizeof(vis)); dfs(0,0); int res=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(!vis[i][j]&&a[i][j])dfs2(i,j),res++; } return res>1; } void solve() { int ans=0,flag=1; for(int i=1;flag;i++,ans++) { if(judge()) { printf("Island splits when ocean rises %d feet. ",ans); return; } flag=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(a[i][j])a[i][j]--,flag=1; } } puts("Island never splits."); } int main() { int cas=1; while(scanf("%d%d",&n,&m)>0) { if(n+m==0)break; memset(a,0,sizeof(a)); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) scanf("%d",&a[i][j]); } printf("Case %d: ",cas++); solve(); } }