题解 CF1344B 【Monopole Magnets】

# 题目分析 N表示北极，S表示南极。 可以发现，N最小的数量就等于黑色方块的连通块数，所以只需要考虑判断-1的情况。 我们可以先考虑要求1：每行每列都得有至少一个S。所以如果有任何一行或一列放不了一个S，那么就得输出-1，否则就是可以的。 如果一个格子是黑色的，那么一定会有N到达这个格子。因此S的同行同列不能有其他段黑色格子。 看图感受一下：   因此，我们只需要用前缀和预处理一下对于 $(i,j)$，从行首、行位、列首、列尾各有多少块黑色方块，然后判断一下即可。 ``` cpp #include<bits/stdc++.h> using namespace std; #define N 1005 int n,m,ans,h1[N][N],l1[N][N],h2[N][N],l2[N][N]; char s[N][N]; bool b[N][N]; inline void dfs(int x,int y)//dfs找联通快 { b[x][y]=1; if(s[x][y-1]=='#' && !b[x][y-1])dfs(x,y-1); if(s[x][y+1]=='#' && !b[x][y+1])dfs(x,y+1); if(s[x-1][y]=='#' && !b[x-1][y])dfs(x-1,y); if(s[x+1][y]=='#' && !b[x+1][y])dfs(x+1,y); } signed 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]=='#' && !b[i][j])dfs(i,j),++ans;//联通快 if(s[i][j]=='#' && s[i-1][j]!='#')l1[i][j]=l1[i-1][j]+1;else l1[i][j]=l1[i-1][j];//预处理 if(s[i][j]=='#' && s[i][j-1]!='#')h1[i][j]=h1[i][j-1]+1;else h1[i][j]=h1[i][j-1]; } } for(int i=n;i>=1;i--) { for(int j=m;j>=1;j--) { if(s[i][j]=='#' && s[i+1][j]!='#')l2[i][j]=l2[i+1][j]+1;else l2[i][j]=l2[i+1][j];//预处理 if(s[i][j]=='#' && s[i][j+1]!='#')h2[i][j]=h2[i][j+1]+1;else h2[i][j]=h2[i][j+1]; } } for(int i=1;i<=n;i++) { bool bbb=0; for(int j=1;j<=m;j++) { if(h1[i][m]==h1[i][j] && h2[i][1]==h2[i][j] && l1[n][j]==l1[i][j] && l2[1][j]==l2[i][j]){bbb=1;break;} } if(!bbb){printf("-1");return 0;}//放不了就输-1 } for(int j=1;j<=m;j++) { bool bbb=0; for(int i=1;i<=n;i++) { if(h1[i][m]==h1[i][j] && h2[i][1]==h2[i][j] && l1[n][j]==l1[i][j] && l2[1][j]==l2[i][j]){bbb=1;break;} } if(!bbb){printf("-1");return 0;}//放不了就输-1 } printf("%d",ans);//输出答案 return 0; } ```