B. Monopole Magnets(思维+连通块)-白红宇

B. Monopole Magnets(思维+连通块)

阅读量：264 次

发布时间：2019-03-01

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

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        #include 
         
          #include 
          
           #include 
           
            #define debug(a) cout << #a << " = " << a << endl;using namespace std;const int maxn = 3000 + 100;typedef long long ll;inline ll read() { ll x = 0, f = 1; char ch = getchar(); while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); } return x * f;}char ma[maxn][maxn];ll fa[maxn*maxn];int dx[4] = {1, 0, -1, 0};int dy[4] = {0, 1, 0, -1};ll n, m;ll get(ll x, ll y) { return (x - 1) * m + y;}ll find(ll x) { if (fa[x] != x) { fa[x] = find(fa[x]); fa[x] = x; }}int main(void) { cin.tie(0); cout.tie(0); std::ios::sync_with_stdio(false); cin >> n >> m; for (ll i = 0; i < maxn*maxn; i++) fa[i] = i; for (ll i = 1; i <= n; i++) { for (ll j = 1; j <= m; j++) { cin >> ma[i][j]; } } bool flag = 1; bool r1 = false; for (ll i = 1; i <= n; i++) { ll num = 0; for (ll j = 1; j <= m; j++) { if (num == 0 && ma[i][j] == '#') num = 1; else if (num == 1 && ma[i][j] == '.') num = 2; else if (num == 2 && ma[i][j] == '#') { flag = 0; break; } } if (num == 0) r1 = true; } for (ll j = 1; j <= m; j++) { ll num = 0; for (ll i = 1; i <= n; i++) { if (num == 0 && ma[i][j] == '#') num = 1; else if (num == 1 && ma[i][j] == '.') num = 2; else if (num == 2 && ma[i][j] == '#') { flag = 0; break; } } if (num == 0) l1 = true; } if (r1 != l1) flag = 0; if (!flag) { cout << "-1" << endl; } else { for (ll i = 1; i <= n; i++) { for (ll j = 1; j <= m; j++) { if (ma[i][j] != '#') continue; for (ll k = 0; k < 4; k++) { ll nx = i + dx[k]; ll ny = j + dy[k]; if (nx < 1 || ny < 1 || nx > n || ny > m) continue; if (ma[nx][ny] == '#' && find(get(nx, ny)) != find(get(i, j))) { fa[find(get(nx, ny))] = find(get(i, j)); } } } } ll ans = 0; for (ll i = 1; i <= n; i++) { for (ll j = 1; j <= m; j++) { if (ma[i][j] == '#' && fa[get(i, j)] == get(i, j)) { ans++; } } } cout << ans << endl; } return 0;}