1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

#include <vector>
#include <unordered_map>

class UnionFind {
public:
    UnionFind(int num) {
        for (int i = 0; i < num; ++i) {
            parent_.push_back(i);
        }
    }

    void unite(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        parent_[pRoot] = qRoot;
    }

    bool connected(int p, int q) {
        return find(p) == find(q);
    }

    int find(int p) {
        if (p != parent_[p]) {
            parent_[p] = find(parent_[p]);
        }
        return parent_[p];
    }

private:
    std::vector<int> parent_;
};

class Solution {
public:
    void solve(std::vector<std::vector<char>>& board) {
        int m = board.size();
        int n = board[0].size();
        UnionFind uf(m * n + 1);
        int dummy = m * n;
        // 先将四条边上为'O'的节点连接起来
        for (int i = 0; i < m; ++i) {
            if (board[i][0] == 'O') {
                uf.unite(dummy, i * n);
            }
            if (board[i][n - 1] == 'O') {
                uf.unite(dummy, i * n + n - 1);
            }
        }
        for (int j = 0; j < n; ++j) {
            if (board[0][j] == 'O') {
                uf.unite(dummy, j);
            }
            if (board[m - 1][j] == 'O') {
                uf.unite(dummy, (m - 1) * n + j);
            }
        }
        // 再将内部相邻的'O'连接起来
        //                                             上      下      左       右
        std::vector<std::vector<int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (int i = 1; i < m - 1; ++i) {
            for (int j = 1; j < n - 1; ++j) {
                if (board[i][j] == 'X') continue;
                for (const auto& dir : directions) {
                    if (board[i + dir[0]][j + dir[1]] == 'X') continue;
                    uf.unite(n * i + j, n * (i + dir[0]) + j + dir[1]);
                }
            }
        }

        // 最后将所有不与dummy连通的'O'设置为'X'即可
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if (board[i][j] == 'O' && !uf.connected(dummy, n * i + j)) {
                    board[i][j] = 'X';
                }
            }
        }
    }
};