Codeforces 1345 D - Monopole Magnets

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 
 5 char a[1010][1010];
 6 bool x[1010],y[1010];       //x记录有#的行，y记录有#的列
 7 int dx[]={1,-1,0,0};
 8 int dy[]={0,0,1,-1};
 9 
10 void dfs(int xx,int yy)
11 {
12     a[xx][yy]='.';
13     for(int i=0;i<4;i++){
14         int xxx=xx+dx[i];
15         int yyy=yy+dy[i];
16         if(a[xxx][yyy]=='#') dfs(xxx,yyy);
17     }
18     return ;
19 }
20 
21 int main()
22 {
23     ios::sync_with_stdio(false);
24     cin.tie(0);
25     cout.tie(0);
26     int n,m;
27     cin>>n>>m;
28     for(int i=0;i<n;i++) cin>>a[i];
29     int flag=1;
30     for(int i=0;i<n;i++){
31         for(int j=0;j<m;j++){
32             if(a[i][j]=='#') {
33                 if(x[i]&&j&&a[i][j-1]!='#'){
34                     flag=0;
35                     break;
36                 }
37                 if(y[j]&&i&&a[i-1][j]!='#'){
38                     flag=0;
39                     break;
40                 }
41                 x[i]=1,y[j]=1;
42             }
43         }
44         if(!flag) break;
45     }
46     int p=0,q=0;
47     for(int i=0;i<n;i++) if(!x[i]) p=1;
48     for(int i=0;i<m;i++) if(!y[i]) q=1;
49     if(p^q) flag=0;     //如果有行没有# 而没有列没有#或者反过来，就输出-1.
50     if(!flag) {cout<<-1<<endl;return 0;}
51     int ans=0;
52     for(int i=0;i<n;i++){
53         for(int j=0;j<m;j++){
54             if(a[i][j]=='#') ans++,dfs(i,j);    //简单的找连通块
55         }
56     }
57     cout<<ans<<endl;
58     return 0;
59 }