D. Monopole Magnets（DFS&构造）

题目传送门

思路：

当一行全为白时,显然这一行极到不了,因为每一行都必须有一个极。假设这个极对应的列存在黑色,显然极要向该极靠近,但极又到不了白色,所以显然这样是无解的,所以存在全白行必须对应全白列.

当一行存在黑色时，黑色必须是连续的一部分,否则该行的极会吸引极越过白色部分到黑色的一端去.对列同理.

其他情况都可以通过在黑色连通块放一个极然后每格都放一个极构造出来。最后答案就是的次数了。

时间复杂度：

AC代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
char mp[N][N];
int n,m,f1,f2,ans,d[4][2]={0,1,0,-1,1,0,-1,0};
void dfs(int x,int y){ //dfs黑色连通块. 
    mp[x][y]='.';
    for(int i=0,nx,ny;i<4;i++){
        nx=x+d[i][0],ny=y+d[i][1];
        if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&mp[nx][ny]=='#')
            dfs(nx,ny);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%s",mp[i]+1);
    for(int i=1;i<=n;i++){
        int c=0;
        for(int j=1;j<=m;j++)
            if(mp[i][j]=='#')
                if(!c||mp[i][j-1]=='.') c++;
        if(c>1) return puts("-1"),0;//特判黑色部分.行同理. 
        if(!c) f1=1;
    }
    for(int j=1;j<=m;j++){
        int c=0;
        for(int i=1;i<=n;i++)
            if(mp[i][j]=='#')
                if(!c||mp[i-1][j]=='.') c++;
        if(c>1) return puts("-1"),0;
        if(!c) f2=1;
    }
    if(f1+f2==1) return puts("-1"),0;//特判全白行,全白列. 
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(mp[i][j]=='#') dfs(i,j),ans++;
    printf("%d\n",ans);
    return 0;
}