题目描述

给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ ，找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

解法一：并查集

这道题通常会用DFS来解，但是也可以用并查集解：首先我们将四条边上的’O’合并成一个连通分量，然后再将圈内的所有相邻的 ‘O’连接起来，最后遍历整个表，将所有为’O’且不与四条边上的’O’所在的连通分量相连的节点设置为’X’即可。

 1#include <vector>
 2#include <unordered_map>
 3
 4class UnionFind {
 5public:
 6    UnionFind(int num) {
 7        for (int i = 0; i < num; ++i) {
 8            parent_.push_back(i);
 9        }
10    }
11
12    void unite(int p, int q) {
13        int pRoot = find(p);
14        int qRoot = find(q);
15        if (pRoot == qRoot) {
16            return;
17        }
18        parent_[pRoot] = qRoot;
19    }
20
21    bool connected(int p, int q) {
22        return find(p) == find(q);
23    }
24
25    int find(int p) {
26        if (p != parent_[p]) {
27            parent_[p] = find(parent_[p]);
28        }
29        return parent_[p];
30    }
31
32private:
33    std::vector<int> parent_;
34};
35
36class Solution {
37public:
38    void solve(std::vector<std::vector<char>>& board) {
39        int m = board.size();
40        int n = board[0].size();
41        UnionFind uf(m * n + 1);
42        int dummy = m * n;
43        // 先将四条边上为'O'的节点连接起来
44        for (int i = 0; i < m; ++i) {
45            if (board[i][0] == 'O') {
46                uf.unite(dummy, i * n);
47            }
48            if (board[i][n - 1] == 'O') {
49                uf.unite(dummy, i * n + n - 1);
50            }
51        }
52        for (int j = 0; j < n; ++j) {
53            if (board[0][j] == 'O') {
54                uf.unite(dummy, j);
55            }
56            if (board[m - 1][j] == 'O') {
57                uf.unite(dummy, (m - 1) * n + j);
58            }
59        }
60        // 再将内部相邻的'O'连接起来
61        //                                             上      下      左       右
62        std::vector<std::vector<int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
63        for (int i = 1; i < m - 1; ++i) {
64            for (int j = 1; j < n - 1; ++j) {
65                if (board[i][j] == 'X') continue;
66                for (const auto& dir : directions) {
67                    if (board[i + dir[0]][j + dir[1]] == 'X') continue;
68                    uf.unite(n * i + j, n * (i + dir[0]) + j + dir[1]);
69                }
70            }
71        }
72
73        // 最后将所有不与dummy连通的'O'设置为'X'即可
74        for (int i = 1; i < m; ++i) {
75            for (int j = 1; j < n; ++j) {
76                if (board[i][j] == 'O' && !uf.connected(dummy, n * i + j)) {
77                    board[i][j] = 'X';
78                }
79            }
80        }
81    }
82};