Monopole Magnets CodeForces - 1345D

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
const int N=1010;
bool x[N],y[N];
char s[N][N];
bool st[N][N];
int n,m;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
void dfs(int x,int y)
{
	st[x][y]=1;
	for(int i=0;i<4;i++)
		for(int j=0;j<4;j++)
		{
			int xx=x+dx[i],yy=y+dy[i];
			if(xx>=0&&xx<n&&yy>=0&&yy<m&&st[xx][yy]==0&&s[xx][yy]==‘#‘)
				dfs(xx,yy);
		}
}
int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)
		cin>>s[i];
	bool flag=1;
	//如果某一行或者某一列存在 那么就要是连续的
	//如果不是这样的话，因为N要在黑块之间移动，那么就必然会经过白块到没有同行或列的另外一部分 
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			if(s[i][j]==‘#‘)
			{
				if(x[i]&&j&&s[i][j-1]!=‘#‘)
				{
					flag=0;
					break;
				}
				if(y[j]&&i&&s[i-1][j]!=‘#‘)
				{
					flag=0;
					break;
				}
				x[i]=y[j]=1;
			}
	//如果有一行或者一列不存在黑块
	//那么行不存在和列不存在 要同时成立
	//然后S放在行和列的相交的部分 
	//因为每行每列至少有一个南磁石。
	int p1=0,p2=0;
	for(int i=0;i<n;i++)
		if(!x[i])
			p1=1;
	for(int i=0;i<m;i++)
		if(!y[i])
			p2=1;
	if(p1^p2)
		flag=0;
	if(flag==0)
	{
		cout<<"-1"<<endl;
		return 0;
	}
	//都满足的话，就是统计连通块的个数了 
	int cnt=0;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			if(s[i][j]==‘#‘&&st[i][j]==0)
			{
				cnt++;
				dfs(i,j);
			}
	cout<<cnt<<endl;
	return 0;
}

Monopole Magnets CodeForces - 1345D

原文：https://www.cnblogs.com/QingyuYYYYY/p/12885636.html