# 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 X``````

After 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 X``````

Tags

Related Problems

Hard Number of Islands II Easy Number of Islands

## 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';
}
}
}

}
}``````

Last updated