Surrounded Regions
Question
Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.
A region is captured by flipping all 'O''s into 'X''s in that surrounded region.
Example
X X X X
X O O X
X X O X
X O X XAfter capture all regions surrounded by 'X', the board should be:
X X X X
X X X X
X X X X
X O X XTags
Breadth First Search Union Find
Related Problems
Hard Number of Islands II Easy Number of Islands
Analysis
本题也是一个多解的问题。
一种比较巧妙的思路是从边缘的'O'出发，通过DFS，所有能够遍历的'O'都可以暂时被标记为'#'，那么剩下未能被标记的'O'说明被surrounded，需要在遍历结束之后全部转为'X'。（用DFS或者BFS要警惕栈溢出）
另一种方法是用Union Find，将与边缘相连通的'O'全部union到一个dummy node（也可以用hasEdge[]来存储，不过内存占用更多）, 最终将没有和这个dummy node是一个component的'O'点全部标记为'X'。
Solution
DFS - (7ms AC 42.74%)
class Solution {
public void solve(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0) return;
int m = board.length;
int n = board[0].length;
// Marking 'O' on the boundary and connected as '*'
for (int i = 0; i < m; i++) {
if (board[i][0] == 'O') {
marking(board, i, 0);
}
if (board[i][n - 1] == 'O') {
marking(board, i, n - 1);
}
}
for (int j = 0; j < n; j++) {
if (board[0][j] == 'O') {
marking(board, 0, j);
}
if (board[m - 1][j] == 'O') {
marking(board, m - 1, j);
}
}
// Replacing 'O' as 'X'
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
}
}
}
// Replacing '*' as 'X'
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == '*') {
board[i][j] = 'O';
}
}
}
}
// DFS marking 'O' as '*'
private void marking (char[][] board, int x, int y) {
int[] dx = {0, 1, 0, -1};
int[] dy = {1, 0, -1, 0};
int nx, ny;
if (board[x][y] == 'O') {
board[x][y] = '*';
for (int i = 0; i < 4; i++) {
nx = x + dx[i];
ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < board.length && ny < board[0].length) {
marking(board, nx, ny);
}
}
}
}
}DFS - (4ms AC 100%)
class Solution {
public void solve(char[][] board) {
if (board.length < 1 || board[0].length < 1)
return;
for (int i = 0; i < board.length; i++) {
if (board[i][0] != 'X');
dfsmarker(i, 0, board);
}
for (int i = 0; i < board.length; i++) {
if (board[i][board[0].length - 1] != 'X')
dfsmarker(i, board[0].length - 1, board);
}
for (int j = 0; j < board[0].length; j++) {
if (board[0][j] != 'X');
dfsmarker(0, j, board);
}
for (int j = 0; j < board[0].length; j++) {
if (board[board.length - 1][j] != 'X')
dfsmarker(board.length - 1, j, board);
}
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
//System.out.println(marker[i][j]);
if (board[i][j] == 'M')
board[i][j] = 'O';
else
board[i][j] = 'X';
}
}
//System.out.println(marker[1][1]);
return;
}
public void dfsmarker(int i, int j, char[][] board) {
if (board[i][j] == 'M' || board[i][j] != 'O')
return;
board[i][j] = 'M';
if (i > 0)
dfsmarker(i - 1, j, board);
if (j > 0)
dfsmarker(i, j - 1, board);
if (i < board.length - 1)
dfsmarker(i + 1, j, board);
if (j < board[0].length - 1)
dfsmarker(i, j + 1, board);
}
}DFS - Cleaner Version (6ms 59.18%)
class Solution {
public void solve(char[][] board) {
if (board.length == 0 || board[0].length == 0) return;
if (board.length < 3 || board[0].length < 3) return;
int m = board.length;
int n = board[0].length;
for (int i = 0; i < m; i++) {
if (board[i][0] == 'O') helper(board, i, 0);
if (board[i][n - 1] == 'O') helper(board, i, n - 1);
}
for (int j = 1; j < n - 1; j++) {
if (board[0][j] == 'O') helper(board, 0, j);
if (board[m - 1][j] == 'O') helper(board, m - 1, j);
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'O') board[i][j] = 'X';
if (board[i][j] == '*') board[i][j] = 'O';
}
}
}
private void helper(char[][] board, int r, int c) {
if (r < 0 || c < 0 || r > board.length - 1 || c > board[0].length - 1 || board[r][c] != 'O') return;
board[r][c] = '*';
helper(board, r + 1, c);
helper(board, r - 1, c);
helper(board, r, c + 1);
helper(board, r, c - 1);
}
}Union Find (20 ms 14.75% AC)
class UnionFind {
private int[] id;
private int[] size;
public UnionFind(int n) {
id = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
id[i] = i;
size[i] = 1;
}
}
public int find(int i) {
while (i != id[i]) {
id[i] = id[id[i]];
i = id[i];
}
return i;
}
public void union(int x, int y) {
int i = find(x);
int j = find(y);
if (i == j) {
return;
}
if (size[i] < size[j]) {
id[i] = j;
size[j] += size[i];
} else {
id[j] = i;
size[i] += size[j];
}
}
public boolean connected(int x, int y) {
return find(x) == find(y);
}
}
public class Solution {
private boolean isEdge(int M, int N, int i, int j) {
return (i == 0 || i == M - 1 || j == 0 || j == N - 1);
}
private boolean insideBoard(int M, int N, int i, int j) {
return (i < M && i >= 0 && j < N && j >= 0);
}
/**
* @param board a 2D board containing 'X' and 'O'
* @return void
*/
public void surroundedRegions(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0) {
return;
}
int M = board.length;
int N = board[0].length;
int[] dirX = {0, 0, -1, 1};
int[] dirY = {-1, 1, 0, 0};
UnionFind uf = new UnionFind(M * N + 1);
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (board[i][j] == 'O') {
if (isEdge(M, N, i, j)) {
uf.union(i * N + j, M * N);
} else {
for (int k = 0; k < 4; k++) {
int x = i + dirX[k];
int y = j + dirY[k];
if (insideBoard(M, N, x, y) && board[x][y] == 'O') {
uf.union(i * N + j, x * N + y);
}
}
}
}
}
}
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (!uf.connected(i * N + j, M * N)) {
board[i][j] = 'X';
}
}
}
}
}Reference
Last updated