题目链接：点击查看

题目大意：给出一个 n * m 的矩阵，' # ' 代表黑色方格，' . ' 代表白色方格，现在可以在任意方格上摆放任意个单向磁铁，磁铁具有的一个性质是：每秒钟 N 极磁铁会向同行或同列的 S 极磁铁靠拢，但 S 极磁铁不会移动，需要构造一种方案，使得：

1. 无论如何移动，N 极磁铁都无法到达白色方格
2. 存在一种移动方案，使得 N 极磁铁可以遍历所有黑色方格
3. 每一行、每一列至少存在一个 S 极磁铁
4. N 极磁铁的个数尽可能少

输出最少的 N 极磁铁的个数

题目分析：图论的题，看完五个样例之后心里大概有点想法了，首先根据第二个样例与其余四个样例的对比，不难看出的一个小结论就是：每一行或每一列至多存在一个黑色方格组成的线段，因为如果存在两个黑色方格组成的线段的话，他们肯定会跨过其中的白色方格可以互相到达，也就是存在一种方案会到达白色方格，与题意不符

再就是通过样例四和样例五可以知道，在满足上面结论的前提下，对于全部都是白色方格的行或列也有限制，如果存在着全白的行，但不存在着全白的列的话，那么全白的行内如果放置 S 极磁铁，就不能满足条件 1 ，如果不放置 S 极磁铁，就不能满足条件 3 ，无论怎么样都不能满足条件，所以是不行的，同理将行和列反过来想也是一样的

只有在满足黑色方格的条件下，不存在这全白的列和行，或者同时存在着全白的列和行才行，如果同时存在着全白的列和行的话，可以将 S 极磁铁放置在全白列和全白行的交界处，这样既能满足条件 1 ，也能满足条件 4

最后总结一下上面的三段话：

1. 每一行或每一列至多存在一个黑色方格组成的线段
2. 不存在着全白的列和行
3. 同时存在着全白的列和行

只有同时满足上述三个条件，题目才存在着解，否则都是 -1 ，这三个条件通过给出的五个样例应该不难分析出来

然后就是如何求解呢，根据样例三可以大胆猜测是需要求连通块的个数，因为 N 极磁铁无法斜着移动，所以每一个连通块内全部放置 S 极磁铁，然后放一个 N 极磁铁就够了

代码：

#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
using namespace std;

typedef long long LL;

typedef unsigned long long ull;

const LL inf=0x3f3f3f3f;

const int N=1e3+100;

const int b[4][2]={0,1,0,-1,1,0,-1,0};

char maze[N][N];

int n,m;

bool check_blank()//检查空白行或列是否满足条件 
{
	bool flag_row=false,flag_col=false;
	for(int i=1;i<=n;i++)
	{
		bool flag=false;
		for(int j=1;j<=m;j++)
		{
			if(maze[i][j]=='#')
			{
				flag=true;
				break;
			}
		}
		if(!flag)
			flag_row=true;//存在空白的一行 
	}
	for(int j=1;j<=m;j++)
	{
		bool flag=false;
		for(int i=1;i<=n;i++)
		{
			if(maze[i][j]=='#')
			{
				flag=true;
				break;
			}
		}
		if(!flag)
			flag_col=true;//存在空白的一列 
	}
	return flag_row&&!flag_col||!flag_row&&flag_col;
}

bool check_black()//检查黑色线段是否满足条件
{
	for(int i=1;i<=n;i++)
	{
		int cnt=0;
		for(int j=1;j<=m;j++)
		{
			if(maze[i][j]=='#')
			{
				cnt++;
				while(j<=m&&maze[i][j]=='#')
					j++;
			}
		}
		if(cnt>1)
			return true;
	}
	for(int j=1;j<=m;j++)
	{
		int cnt=0;
		for(int i=1;i<=n;i++)
		{
			if(maze[i][j]=='#')
			{
				cnt++;
				while(i<=n&&maze[i][j]=='#')
					i++;
			}
		}
		if(cnt>1)
			return true;
	}
	return false;
}

void dfs(int x,int y)//dfs求连通块
{
	maze[x][y]='.';
	for(int i=0;i<4;i++)
	{
		int xx=x+b[i][0];
		int yy=y+b[i][1];
		if(xx<=0||yy<=0||xx>n||yy>m)
			continue;
		if(maze[xx][yy]=='.')
			continue;
		dfs(xx,yy);
	}
}

int main()
{
#ifndef ONLINE_JUDGE
//	freopen("input.txt","r",stdin);
//	freopen("output.txt","w",stdout);
#endif
//	ios::sync_with_stdio(false);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%s",maze[i]+1);
	if(check_blank()||check_black())
		return 0*puts("-1");
	int ans=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(maze[i][j]=='#')
			{
				ans++;
				dfs(i,j);
			}
	printf("%d\n",ans);







    return 0;
}