# 130. Surrounded Regions (Medium)

https://leetcode.com/problems/surrounded-regions/

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.

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

Explanation:

Surrounded regions shouldn’t be on the border, which means that any `'O'` on the border of the board are not flipped to `'X'`. Any `'O'` that is not on the border and it is not connected to an `'O'` on the border will be flipped to `'X'`. Two cells are connected if they are adjacent cells connected horizontally or vertically.

## Solutions

``````class Solution {
public void solve(char[][] board) {
if (board == null || board.length <= 2 || board[0] == null || board[0].length <= 2) {
return;
}

int rows = board.length;
int cols = board[0].length;

// Any 'O' connected to a boundary can't be turned to 'X'
// Any 'O' connected to a boundary 'O' directly can't be turned
// Any 'O' connected to a boundary 'O' through other 'O' can't be turned

// Start from first and last column, turn 'O' to '*' and start infection
for (int i = 0; i < rows; i++) {
if (board[i][0] == 'O') {
infect(board, i, 0, rows, cols);
}

if (board[i][cols - 1] == 'O') {
infect(board, i, cols - 1, rows, cols);
}
}

// Start from first and last row, turn '0' to '*' and start infection
for (int j = 0; j < cols; j++) {
if (board[0][j] == 'O') {
infect(board, 0, j, rows, cols);
}

if (board[rows - 1][j] == 'O') {
infect(board, rows - 1, j, rows, cols);
}
}

// post-prcessing, turn 'O' to 'X', '*' back to 'O', keep 'X' intact.
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
}

if (board[i][j] == '*') {
board[i][j] = 'O';
}
}
}
}

// Use DFS to turn internal however boundary-connected 'O' to '*';
private void infect(char[][] board, int i, int j, int rows, int cols) {
// Out of the boundary
if (i < 0 || i >= rows || j < 0 || j >= cols) {
return;
}

// Not infectable or already infected.
if (board[i][j] != 'O') {
return;
}

board[i][j] = '*'; // Mark the connected cell with '*'.

// infect cells in four directions
infect(board, i + 1, j, rows, cols);
infect(board, i - 1, j, rows, cols);
infect(board, i, j + 1, rows, cols);
infect(board, i, j - 1, rows, cols);
}
}
``````