黑白方格

题意解析

使用 $\tt{BFS/DFS}$ 或者 $\tt{并查集}$ 所有不同的连通块进行标记。

统计网格中连通块的数量记为 $k$，白色方格的数量为 $w$。

遍历所有 $\tt{白色}$ 方格，统计每个白色方格周围不同的连通块数量，记为 $c_i$，那么如果将当前方格染为 $\tt{黑色}$，网格上的连通块的数量变为为 $k - c_i + 1$。求出所有的 $k - c_i + 1$，最后的答案为 $\frac{{\sum_{i=1}^{w}{k - c_i + 1}}}{w}$。

AC代码

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

using i64 = long long;

constexpr int dirs[][2] {0, 1, 1, 0, 0, -1, -1, 0};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<string> grid(n);
    for (auto &row : grid)
        cin >> row;
    vector<vector<int>> color(n, vector<int>(m));
    int k = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] != 'B' or color[i][j]) continue;
            queue<pair<int, int>> q;
            q.emplace(i, j);
            color[i][j] = ++k;
            while (!q.empty()) {
                auto [r, c] = q.front(); q.pop();
                for (auto &[dr, dc] : dirs) {
                    int nr = r + dr, nc = c + dc;
                    if (nr < 0 or nr >= n or nc < 0 or nc >= m) continue;
                    if (grid[nr][nc] != 'B' or color[nr][nc]) continue;
                    color[nr][nc] = color[r][c];
                    q.emplace(nr, nc);
                }
            }
        }
    }
    i64 a = 0, b = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] != 'W') continue;
            set<int> st;
            for (auto &[dr, dc] : dirs) {
                int nr = i + dr, nc = j + dc;
                if (nr < 0 or nr >= n or nc < 0 or nc >= m) continue;
                if (grid[nr][nc] == 'W') continue;
                st.insert(color[nr][nc]);
            }
            a += k - st.size() + 1;
            b += 1;
        }
    cout << setprecision(12) << fixed << a * 1.0 / b << '\n';
    return 0;
}

复杂度分析

使用 $\tt{BFS/DFS}$ 标记网格中所有的连通块的时间复杂度为 $\mathrm{O}(N \times M)$。
枚举 $\tt{白色}$ 方格的时间复杂度为 $\mathrm{O}(N \times M)$。