题目描述
给你一个
m x n
的矩阵board
,由若干字符 ‘X’ 和 ‘O’ ,找到所有被 ‘X’ 围绕的区域,并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。
解法一:并查集
这道题通常会用DFS来解,但是也可以用并查集解:首先我们将四条边上的’O’合并成一个连通分量,然后再将圈内的所有相邻的 ‘O’连接起来,最后遍历整个表,将所有为’O’且不与四条边上的’O’所在的连通分量相连的节点设置为’X’即可。
#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';
}
}
}
}
};
评论