题意
度度熊是一个喜欢计算机的孩子，在计算机的世界中，所有事物实际上都只由0和1组成。
现在给你一个$n*m$的图像，你需要分辨他究竟是$0$，还是$1$，或者两者均不是。
- 图像$0$的定义：存在$1$字符且$1$字符只能是由一个连通块组成，存在且仅存在一个由$0$字符组成的连通块完全被$1$所包围。
- 图像$1$的定义：存在$1$字符且$1$字符只能是由一个连通块组成，不存在任何$0$字符组成的连通块被$1$所完全包围。
连通的含义是，只要连续两个方块有公共边，就看做是连通。
完全包围的意思是，该连通块不与边界相接触。
思路
维护并查集。
对于$0$，如果在边界上，则与$0$合并，否则正常合并。
对于$1$，按正常并查集进行操作即可。
最后只需check一下是否满足条件。
写得太丑了。。。
代码
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>
#include <map>
#include <set>
//#define test
using namespace std;
const int Nmax=1e3+7;
typedef long long ll;
int dx[]={0,0,0,1,-1};
int dy[]={0,1,-1,0,0};
int n,m;
int mp[Nmax][Nmax];
int id(int x,int y)
{
return (x-1)*m+y;
}
int fa[Nmax*Nmax];
int find(int x)
{
if(fa[x]!=x)
fa[x]=find(fa[x]);
return fa[x];
}
void merge(int a,int b)
{
int r1=find(a),r2=find(b);
if(r1!=r2)
fa[r1]=r2;
}
void init()
{
for(int i=0;i<=n*m+10;i++)
fa[i]=i;
}
vector<int> check[3];
int es(int x,int cc)
{
for(int i=0;i<(int)check[cc].size();i++)
{
if(x==check[cc][i])
return 1;
}
return 0;
}
int is1()
{
int r0=find(0);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(mp[i][j])
continue;
int now=find(id(i,j));
if(now!=r0)
return 0;
}
}
return 1;
}
int check_one()
{
check[1].clear();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(!mp[i][j])
continue;
int now=find(id(i,j));
if(es(now,mp[i][j]))
continue;
else
check[1].push_back(now);
if(check[1].size()>=2)
return 0;
}
}
if(check[1].size()!=1)
return 0;
return 1;
}
int is0()
{
int r0=find(0);
int ct0=0;
check[0].clear();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(mp[i][j])
continue;
int now=find(id(i,j));
if(es(now,0))
continue;
else
check[0].push_back(now);
if(check[0].size()>=3)
return 0;
}
}
if(check[0].size()>=3)
return 0;
for(int i=0;i<(int)check[0].size();i++)
{
if(check[0][i]!=r0)
ct0++;
}
if(ct0!=1)
return 0;
return 1;
}
int main()
{
#ifdef test
#endif
char c;
//freopen("6.in","r",stdin);
while(~scanf("%d%d",&n,&m))
{
getchar();
//printf("%d %d\n",n,m);
init();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
c=getchar();
mp[i][j]=c-'0';
}
getchar();
}
//for(int i=1;i<=n;i++)
//for(int j=1;j<=m;j++)
//printf("%d%c",mp[i][j],j==m?'\n':' ');
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
for(int k=1;k<=4;k++)
{
int nowx=i+dx[k],nowy=j+dy[k];
if(!mp[i][j])
{
if(nowx<1 || nowy<1 || nowx>n || nowy>m)
merge(id(i,j),0);
else
{
if(!mp[nowx][nowy])
{
merge(id(i,j),id(nowx,nowy));
}
}
}
else
{
if(nowx<1 || nowy<1 || nowx>n || nowy>m)
continue;
//merge(id(i,j),n*m+3);
else
{
if(mp[nowx][nowy])
{
merge(id(i,j),id(nowx,nowy));
}
}
}
}
}
}
if(!check_one())
printf("-1\n");
else if(is0())
printf("0\n");
else if(is1())
printf("1\n");
else
printf("-1\n");
}
return 0;
}
