官方题解｜棋子的气

题目解析

一颗棋子的气就是它上下左右 「空点」的数量。

若一颗棋子不和其他棋子共享气，我们直接统计下其周围的「空点」的数量即可；

如果棋子和其他棋子共享气，那么我们可以使用 $\tt{DFS/BFS}$ 把这一整块共享气的棋子全部找出来，然后把这些棋子周围的空点数量 $X$ 统计出来，那么对于这块共享气的棋子每个棋子的气都是 $X$。

AC代码

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

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

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n; cin >> n;
    vector<string> board(n);
    for (auto &row : board) cin >> row;
    vector<vector<int>> res(n, vector<int>(n));
    vector<vector<int>> st(n, vector<int>(n));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) {
            if (board[i][j] == '.' or st[i][j]) continue;
            vector<pair<int, int>> stone;
            queue<pair<int, int>> q;
            q.emplace(i, j);
            st[i][j] = 1;
            while (!q.empty()) {
                auto [r, c] = q.front(); q.pop();
                stone.emplace_back(r, c);
                for (auto &[dr, dc] : dirs) {
                    int nr = r + dr, nc = c + dc;
                    if (nr < 0 or nr >= n or nc < 0 or nr >= n) continue;
                    if (board[nr][nc] != board[r][c]) continue;
                    if (st[nr][nc]) continue;
                    q.emplace(nr, nc);
                    st[nr][nc] = 1;
                }
            }
            set<pair<int, int>> liberty;
            for (auto &[r, c] : stone) {
                for (auto &[dr, dc] : dirs) {
                    int nr = r + dr, nc = c + dc;
                    if (nr < 0 or nr >= n or nc < 0 or nr >= n) continue;
                    if (board[nr][nc] != '.') continue;
                    liberty.emplace(nr, nc);
                }
            }
            for (auto &[r, c] : stone)
                res[r][c] = liberty.size();
        }
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            cout << res[i][j] << " \n"[j + 1 == n];
    return 0;
}

复杂度分析

使用 $\tt{DFS/BFS}$ 找出所有一个棋子及其共享气的棋子总的时间复杂度为 $\mathrm{O}(N^2)$；
使用 std::set 找出这块棋子周围的空点数量的时间复杂度为 $\mathrm{O}(N^2 \log{N^2})$。
总的时间复杂度为 $\mathrm{O}(N^2 \log{N^2})$。