CF 1344 B Monopole Magnets 分析+dfs判联通快
这个黑色块肯定都是凸的。
即：黑色格子必须在中间，否则两边都有S会吸到中间的白色。
然后就是不能只有空行，或只有空列。否则会出现这一行或这一列S无法放的情况。
上述2个条件满足后，dfs算联通块即可。
#include
using namespace std;
typedef long long ll;
#define ls (o<<1)
#define rs (o<<1|1)
#define pb push_back
const double PI= acos(-1.0);
const int M = 1e5+7;
/*
int head[M],cnt;
void init(){cnt=0,memset(head,0,sizeof(head));}
struct EDGE{int to,nxt,val;}ee[M*2];
void add(int x,int y){ee[++cnt].nxt=head[x],ee[cnt].to=y,head[x]=cnt;}
*/
char s[1010][1010];
int zo[1010];//某一行列是否是空
int n,m;
void dfs(int x,int y)
{
if(xn||ym||s[x][y]=='.')return ;
s[x][y]='.';
dfs(x+1,y);
dfs(x-1,y);
dfs(x,y+1);
dfs(x,y-1);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(int i=1;i>(s[i]+1);
int ans=0;
bool f=true;
int sm=0,a=0,b=0;
for(int i=1;i<=n;i++)
{
int nm=0,l=m+1,r=0;
for(int j=1;j<=m;j++)
{
if(s[i][j]=='#')
{
nm++;
l=min(l,j);
r=max(r,j);
sm++;
}
}
if(nm==0)a++;
else if(r-l+1!=nm)f=false;
}
for(int i=1;i<=m;i++)
{
int nm=0,l=n+1,r=0;
for(int j=1;j<=n;j++)
{
if(s[j][i]=='#')
{
nm++;
l=min(l,j);
r=max(r,j);
}
}
if(nm==0)b++;
else if(r-l+1!=nm)f=false;
}
int z=0;if(a==0)z++;if(b==0)z++;
if(z==1)f=false;
if(sm==0)f=true;
if(f)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(s[i][j]=='#')
{
dfs(i,j);
ans++;
}
}
}
else ans=-1;
cout<<ans<<endl;
return 0;
}
夕林山寸
原创文章 399获赞 21访问量 2万+
关注
私信
展开阅读全文
作者：夕林山寸
