[CF1344B] Monopole Magnets

Description

有一个 (n imes m) 的方格图，格子被染成了黑色或者白色。要在里面放一些单极磁铁，一个格子内可以放置多个磁铁。

定义磁铁的吸引：如果 N 与 S 处在同一行/列中，那么 N 会向着 S 的方向移动一格。

每行每列至少有一个 S。

对于每个黑色格子，至少存在一个 N 使得经过一系列吸引操作可以经过它。

对于每个白色格子，不存在任何一个 N 使得经过系列吸引操作可以经过它。

求至少需要几个 N 磁铁。

Solution

对于每个黑色连通块，暴力把每个格子放上 S，那么这个连通块中只要放一个 N，这个连通块就 OK 了。

一行/列中，不能存在两个不相邻的黑色块（因为每行每列至少有一个 S）。

一个格子可以放 S，当且仅当它是黑，或者它所在行列均没有黑。同时我们要求每行每列都至少有一个 S，因此还需要根据这个条件检验一下。

综上所述，我们首先判断每行/列中是否存在两个不相邻的黑块，然后判断对于每行每列是否都至少存在一个位置满足它是黑，或者它所在行列均没有黑。如果成立，那么我们输出黑色连通块的个数即可。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;

    vector<vector<int>> a(n + 2);
    for (auto &i : a)
        i.resize(m + 2);

    vector<vector<int>> b(n + 2);
    for (auto &i : b)
        i.resize(m + 2);

    vector<vector<int>> vis(n + 2);
    for (auto &i : vis)
        i.resize(m + 2);

    for (int i = 1; i <= n; i++)
    {
        string tmp;
        cin >> tmp;
        for (int j = 1; j <= m; j++)
        {
            char ch = tmp[j - 1];
            if (ch == '#')
                a[i][j] = 0;
            else
                a[i][j] = 1;
        }
    }

    for (int i = 1; i <= n; i++)
    {
        vector<int> tmp;
        for (int j = 1; j <= m; j++)
        {
            if (a[i][j] == 0)
                tmp.push_back(j);
        }
        for (int j = 1; j < tmp.size(); j++)
        {
            if (tmp[j] != tmp[j - 1] + 1)
            {
                cout << -1 << endl;
                return 0;
            }
        }
    }

    for (int j = 1; j <= m; j++)
    {
        vector<int> tmp;
        for (int i = 1; i <= n; i++)
        {
            if (a[i][j] == 0)
                tmp.push_back(i);
        }
        for (int i = 1; i < tmp.size(); i++)
        {
            if (tmp[i] != tmp[i - 1] + 1)
            {
                cout << -1 << endl;
                return 0;
            }
        }
    }


    vector<int> blackcount_row(n + 2);
    vector<int> blackcount_col(m + 2);

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (a[i][j])
                continue;
            blackcount_row[i]++;
            blackcount_col[j]++;
        }
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (a[i][j] == 0 || (blackcount_row[i] == 0 && blackcount_col[j] == 0))
            {
                b[i][j] = 1;
            }
        }
    }

    for (int i = 1; i <= n; i++)
    {
        int cnt = 0;
        for (int j = 1; j <= m; j++)
            cnt += b[i][j];
        if (cnt == 0)
        {
            cout << -1 << endl;
            return 0;
        }
    }

    for (int j = 1; j <= m; j++)
    {
        int cnt = 0;
        for (int i = 1; i <= n; i++)
        {
            cnt += b[i][j];
        }
        if (cnt == 0)
        {
            cout << -1 << endl;
            return 0;
        }
    }

    auto check = [n, m](int i, int j) -> bool {
        return i >= 1 && j >= 1 && i <= n && j <= m;
    };

    function<void(int, int)> dfs = [&](int i, int j) {
        static const int dx[] = {1, -1, 0, 0};
        static const int dy[] = {0, 0, 1, -1};

        vis[i][j] = 1;

        for (int d = 0; d < 4; d++)
        {
            int ni = i + dx[d];
            int nj = j + dy[d];
            if (check(ni, nj) && vis[ni][nj] == 0 && a[i][j] == 0)
            {
                dfs(ni, nj);
            }
        }
    };

    int cnt = 0;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (a[i][j] == 0 && vis[i][j] == 0)
            {
                dfs(i, j);
                ++cnt;
            }
        }
    }

    cout << cnt << endl;
}