本文共 1740 字，大约阅读时间需要 5 分钟。

ps：说实话这场cf质量真不咋地，最讨厌的就是出成阅读理解题，打比赛是为了让选手的算法能力得到提升，不知道出成阅读理解题是几个意思，毫无意义，C和D都看了半天才看懂。 题意：给你一个网格，网格中的 每个格子为黑色或者白色，你要放置一些S磁铁，N磁铁。N磁铁会走向同一行或者同一列的S磁铁，然后N磁铁只能经过黑色的格子，不能经过白色的格子。然后求对于所有的操作，就是一个N磁铁会被无限个若干的S磁铁吸引，而且N磁铁要经过所有的黑色格子，并且每一行每一列都至少有一个磁铁，问你最少的N磁铁放置多少个。 思路：我们重点考虑一下什么情况下为-1，这里解释一下样例2，对于样例2的第一张图，你可能以为N只要往右走再往下走不就能走完所有黑格子，并且不会走到任何一个白色格子，一开始我也这样以为的，结果就陷入了死循环，死活看不懂样例。其实题目说的是对于所有的情况都得满足，所有样例2第一幅图有黑色格子的话它就必须往下走，这样就会经过白色格子，于是就-1了。 然后只有3钟情况会-1. 1、同行或同列的任意两个黑色格子之间有白色格子。 2、存在一行全白但不存在一列全白 3、存在一列全白但不存在一行全白 排除了-1的情况后就很好做了，只要dfs或bfs求一个黑色格子的连通块个数就可以了，因为每个连通块放一个就可以了。

#include
   
    using namespace std;typedef long long ll;const int maxn=1005;const int dir[4][2]={
   {
   1,0},{
   -1,0},{
   0,1},{
   0,-1}};int n,m,ans,vis[maxn][maxn],visx[maxn],visy[maxn];char s[maxn][maxn];void bfs(int x,int y){
   	queue
    
     
      >q;	vis[x][y]=1;	q.push({
   x,y});	while(!q.empty())	{
   		pair
      
        t=q.front();		q.pop();		int x=t.first,y=t.second;		for(int i=0;i<4;++i)		{
   			int nx=x+dir[i][0],ny=y+dir[i][1];			if(nx<1||nx>n||ny<1||ny>m||vis[nx][ny]||s[nx][ny]=='.') continue;			q.push({
   nx,ny});			vis[nx][ny]=1;		}	}}int main(){
   	scanf("%d %d",&n,&m);	for(int i=1;i<=n;++i) scanf("%s",s[i]+1);	for(int i=1;i<=n;++i)		for(int j=1;j<=m;++j)		{
   			if(s[i][j]=='#')			{
   				if(visx[i]&&j-visx[i]>1){
   					puts("-1");return 0;				}				if(visy[j]&&i-visy[j]>1)				{
   					puts("-1");return 0;				}				visx[i]=j,visy[j]=i;			 } 		}	int flag1=0,flag2=0;	for(int i=1;i<=n;++i) if(!visx[i]) {
   flag1=1;break;}	for(int i=1;i<=m;++i) if(!visy[i]) {
   flag2=1;break;}	if(flag1^flag2){
   		puts("-1");return 0;	}	for(int i=1;i<=n;++i)	for(int j=1;j<=m;++j)	if(!vis[i][j]&&s[i][j]=='#') {
   	ans++,bfs(i,j);}	printf("%d\n",ans); }
      
     
    
   

转载地址：http://bbign.baihongyu.com/