Given a 2D board containing'X'and'O'(the letter O), capture all regions surrounded by'X'.
A region is captured by flipping all'O's into'X's in that surrounded region.
For example,
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X
2. Implementation
(1) Union Find
思路:
(1) 用Union Find的方法，将 n * m作为一个特殊的parent id，表示所有与边连接的component的root
(2) 对于board上所有"O"，如果它在边上，则与 n * m的parent id union,否则将其四周的'O‘, 与其union
(3)
class Solution {
public void solve(char[][] board) {
if (board == null || board.length == 0) {
return;
}
int m = board.length, n = board[0].length;
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
UnionFind uf = new UnionFind(n * m + 1);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'X') continue;
if (i == 0 || i == m - 1 || j == 0 ||j == n - 1) {
uf.union(i * n + j, n * m);
}
else {
for (int[] direction : directions) {
int nextRow = i + direction[0];
int nextCol = j + direction[1];
if (board[nextRow][nextCol] == 'O') {
uf.union(nextRow * n + nextCol, i * n + j);
}
}
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (!uf.isConnected(i * n + j, n * m)) {
board[i][j] = 'X';
}
}
}
}
class UnionFind {
int[] parents;
int[] size;
public UnionFind(int n) {
parents = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parents[i] = i;
size[i] = 1;
}
}
public int find(int id) {
while (id != parents[id]) {
id = parents[id];
}
return id;
}
public boolean isConnected(int i, int j) {
return find(i) == find(j);
}
public void union(int i, int j) {
int rootI = find(i);
int rootJ = find(j);
if (rootI == rootJ) return;
if (size[rootI] < size[rootJ]) {
parents[rootI] = rootJ;
size[rootJ] += size[rootI];
}
else {
parents[rootJ] = rootI;
size[rootI] += size[rootJ];
}
}
}
}