## Algorithm

Problem Name: 130. Surrounded Regions

Given an `m x n` matrix `board` containing `'X'` and `'O'`, capture all regions that are 4-directionally surrounded by `'X'`.

A region is captured by flipping all `'O'`s into `'X'`s in that surrounded region.

Example 1:

```Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
Explanation: Notice that an 'O' should not be flipped if:
- It is on the border, or
- It is adjacent to an 'O' that should not be flipped.
The bottom 'O' is on the border, so it is not flipped.
The other three 'O' form a surrounded region, so they are flipped.
```

Example 2:

```Input: board = [["X"]]
Output: [["X"]]
```

Constraints:

• `m == board.length`
• `n == board[i].length`
• `1 <= m, n <= 200`
• `board[i][j]` is `'X'` or `'O'`

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
void solve(vector<vector<char>>& board) {
if(board.empty()) return;
int m = board.size(), n = board[0].size();
vector<vector < int>>visited(m, vector<int>(n, 0));
for(int i = 0; i  <  m; i++)
for(int j = 0; j  <  n; j++){
if(visited[i][j] || board[i][j] == 'X') continue;
bool surrounded = DFS(board, visited, i, j, m, n);
if(surrounded) replace(board, i, j, m, n);
}
}

bool DFS(vector < vector<char>>& board, vector < vector<int>>& visited, int r, int c, int m, int n){
if(r  <  0 || r == m || c < 0 || c == n) return false;
if(board[r][c] == 'X' || visited[r][c]) return true;
visited[r][c] = 1;
bool L = DFS(board, visited, r, c - 1, m, n);
bool R = DFS(board, visited, r, c + 1, m, n);
bool U = DFS(board, visited, r - 1, c, m, n);
bool D = DFS(board, visited, r + 1, c, m, n);
return L && R && U && D;
}

void replace(vector < vector<char>>& board, int r, int c, int m, int n){
if(r  <  0 || r == m || c < 0 || c == n || board[r][c] == 'X') return;
board[r][c] = 'X';
replace(board, r + 1, c, m, n);
replace(board, r - 1, c, m, n);
replace(board, r, c + 1, m, n);
replace(board, r, c - 1, m, n>;
}
};
``````
Copy The Code &

Input

cmd
board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]

Output

cmd
[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public void solve(char[][] board) {
if (board == null || board.length == 0) {
return;
}
int rows = board.length;
int cols = board[0].length;
List < List();
for (int r = 0; r  <  rows; r++) {
}
for (int c = 0; c  <  cols; c++) {
}
for (List < Integer> border : borders) {
dfs(board, border.get(0), border.get(1), rows, cols);
}
for (int r = 0; r  <  rows; r++) {
for (int c = 0; c  <  cols; c++) {
if (board[r][c] == 'O') {
board[r][c] = 'X';
}
if (board[r][c] == 'E') {
board[r][c] = 'O';
}
}
}
}

private void dfs(char[][] board, int row, int col, int rows, int cols) {
if (board[row][col] != 'O') {
return;
}
board[row][col] = 'E';
if (col  <  cols - 1) {
dfs(board, row, col + 1, rows, cols);
}
if (row < rows - 1) {
dfs(board, row + 1, col, rows, cols);
}
if (col > 0) {
dfs(board, row, col - 1, rows, cols);
}
if (row > 0) {
dfs(board, row - 1, col, rows, cols);
}
}
}
``````
Copy The Code &

Input

cmd
board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]

Output

cmd
[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const solve = function(board) {
if (!board || board.length < 3 || board[0].length < 3) return;
let r = board.length;
let c = board[0].length;
for (let i = 0; i  <  c; i++) {
if (board[0][i] === "O") search(board, 0, i);
if (board[r - 1][i] === "O") search(board, r - 1, i);
}
for (let i = 0; i  <  r; i++) {
if (board[i][0] === "O") search(board, i, 0);
if (board[i][c - 1] === "O") search(board, i, c - 1);
}
for (let i = 0; i  <  r; i++) {
for (let j = 0; j  <  c; j++) {
if (board[i][j] === "O") board[i][j] = "X";
if (board[i][j] === "*") board[i][j] = "O";
}
}
};

function search(board, i, j) {
if (i  <  0 || j < 0 || i >= board.length || j >= board[0].length) return;
if (board[i][j] !== "O") return;
board[i][j] = "*";
search(board, i + 1, j);
search(board, i - 1, j);
search(board, i, j + 1);
search(board, i, j - 1);
}
``````
Copy The Code &

Input

cmd
board = [["X"]]

Output

cmd
[["X"]]

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def solve(self, board: List[List[str]]) -> None:
m, n = len(board), len(board and board[0])

def explore(i, j):
board[i][j] = "S"
for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
if 0 <= x < m and 0 <= y < n and board[x][y] == "O":
explore(x, y)

for i in range(max(m, n)):
if i < m and board[i][0] == "O":
explore(i, 0)
if i < m and board[i][n - 1] == "O":
explore(i, n - 1)
if i < n and board[0][i] == "O":
explore(0, i)
if i < n and board[m - 1][i] == "O":
explore(m - 1, i)
for i in range(m):
for j in range(n):
if board[i][j] == "S":
board[i][j] = "O"
elif board[i][j] == "O":
board[i][j] = "X"
``````
Copy The Code &

Input

cmd
board = [["X"]]

Output

cmd
[["X"]]

### #5 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _0130_SurroundedRegions
{
public void Solve(char[][] board)
{
int m = board.Length;
if (m  <  3) return;
int n = board[0].Length;
if (n  <  3) return;

var 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 (i == 0 || i == m - 1 || j == 0 || j == n - 1)
uf.Union(i * n + j, m * n);
else
{
if (board[i - 1][j] == 'O')
uf.Union(i * n + j, (i - 1) * n + j);
if (board[i + 1][j] == 'O')
uf.Union(i * n + j, (i + 1) * n + j);
if (board[i][j - 1] == 'O')
uf.Union(i * n + j, i * n + j - 1);
if (board[i][j + 1] == 'O')
uf.Union(i * n + j, i * n + j + 1);
}

int pIndex = uf.Find(m * n);

for (int i = 0; i  <  m; i++)
for (int j = 0; j  <  n; j++)
if (uf.Find(i * n + j) != pIndex)
board[i][j] = 'X';
}

public class UnionFind
{
private int[] parents;
private int[] ranks;

public UnionFind(int count)
{
parents = new int[count];
ranks = new int[count];

for (int i = 0; i  <  count; i++)
parents[i] = i;
}

public int Find(int index)
{
if (parents[index] != index)
parents[index] = Find(parents[index]);

return parents[index];
}

public void Union(int index1, int index2)
{
var pIndex1 = Find(index1);
var pIndex2 = Find(index2);

if (pIndex1 == pIndex2) return;
if (ranks[pIndex1] >= ranks[pIndex2])
{
parents[pIndex2] = pIndex1;
ranks[pIndex2]++;
}
else
{
parents[pIndex1] = pIndex2;
ranks[pIndex1]++;
}
}
}
}
}
``````
Copy The Code &

Input

cmd
board = [["X"]]

Output

cmd
[["X"]]