度度熊的01世界
Accepts: 967
Submissions: 3064
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
Problem Description
度度熊是一个喜欢计算机的孩子，在计算机的世界中，所有事物实际上都只由0和1组成。
现在给你一个n*m的图像，你需要分辨他究竟是0，还是1，或者两者均不是。
图像0的定义：存在1字符且1字符只能是由一个连通块组成，存在且仅存在一个由0字符组成的连通块完全被1所包围。
图像1的定义：存在1字符且1字符只能是由一个连通块组成，不存在任何0字符组成的连通块被1所完全包围。
连通的含义是，只要连续两个方块有公共边，就看做是连通。
完全包围的意思是，该连通块不与边界相接触。
Input
本题包含若干组测试数据。 每组测试数据包含： 第一行两个整数n,m表示图像的长与宽。 接下来n行m列将会是只有01组成的字符画。
满足1<=n,m<=100
Output
如果这个图是1的话，输出1；如果是0的话，输出0，都不是输出-1。
一道搜索题，为了防止边界判断的问题，我们不妨将地图向外拓展一圈0，将大小(1,1)->(n,m)的图转化为(0,0)->(n+1,m+1)的图，
首先分类讨论一下，如果这个数字是零，那么'0'联通块有两个，'1'联通块有一个。
如果这个数字是一，那么'0'联通块有一个，'1'联通块有一个。
其他情况表示既不是0也不是1.
我们可以先dfs填充'0'为'2',再继续填充'1'，找到这两个值然后判断一下就好了。
#include<bits/stdc++.h> using namespace std; #define inf 0x3f3f3f3f #define LL long long int e[105][105],n,m; int fx[4][2]={1,0,-1,0,0,1,0,-1}; int d1,d2,d3,d4,N1,N2; void dfs(int x,int y) { e[x][y]=2; for(int i=0;i<4;++i) { int dx=x+fx[i][0]; int dy=y+fx[i][1]; if(dx<d1||dy<d2||dx>d3||dy>d4||e[dx][dy]==N1||e[dx][dy]==N2) continue; dfs(dx,dy); } } int main() { int i,j,k; // freopen("in.txt","r",stdin); while(cin>>n>>m){memset(e,0,sizeof(e)); char x; for(i=1;i<=n;++i) { for(j=1;j<=m;++j){ cin>>x; e[i][j]=x-'0'; } } int s=1,s2=0; d1=0,d2=0,d3=n+1,d4=m+1; N1=1;N2=2; dfs(0,0); for(i=1;i<=n;++i) for(j=1;j<=m;++j) if(e[i][j]==0) {dfs(i,j);s++;} N1=2; for(i=1;i<=n;++i) for(j=1;j<=m;++j) if(e[i][j]==1) {dfs(i,j);s2++;} if(s==2&&s2==1) puts("0"); else if(s==1&&s2==1) puts("1"); else puts("-1"); } return 0; }