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;}

这段代码实现了一个棋盘问题的解决方案。代码首先读取输入数据，初始化相关变量和数组，然后通过深度优先搜索（DFS）来标记各个连通区域。接着，代码检查棋盘是否存在不连续的黑色块，以及是否存在全空的行或列。最后，根据检查结果，计算棋盘中可以放置的极数。

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

你可能感兴趣的文章