# Surrounded Regions Leetcode Solution

In this post, we are going to solve the Surrounded Regions Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.

## Problem

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

Now, lets see the leetcode solution of Surrounded Regions Leetcode Solution.

### Surrounded Regions Leetcode Solution in Python

```class Solution:
def solve(self, board: List[List[str]]) -> None:
if not board:
return

m = len(board)
n = len(board[0])
dirs = [0, 1, 0, -1, 0]
q = deque()

for i in range(m):
for j in range(n):
if i * j == 0 or i == m - 1 or j == n - 1:
if board[i][j] == 'O':
q.append((i, j))
board[i][j] = '*'

# Mark grids that stretch from four sides with '*'
while q:
i, j = q.popleft()
for k in range(4):
x = i + dirs[k]
y = j + dirs[k + 1]
if x < 0 or x == m or y < 0 or y == n:
continue
if board[x][y] != 'O':
continue
q.append((x, y))
board[x][y] = '*'

for row in board:
for i, c in enumerate(row):
row[i] = 'O' if c == '*' else 'X'```

### Surrounded Regions Leetcode Solutionin CPP

```class Solution {
public:
void solve(vector<vector<char>>& board) {
if (board.empty())
return;

const int m = board.size();
const int n = board[0].size();
const vector<int> dirs{0, 1, 0, -1, 0};
queue<pair<int, int>> q;

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (i * j == 0 || i == m - 1 || j == n - 1)
if (board[i][j] == 'O') {
q.emplace(i, j);
board[i][j] = '*';
}

// Mark grids that stretch from four sides with '*'
while (!q.empty()) {
const auto [i, j] = q.front();
q.pop();
for (int k = 0; k < 4; ++k) {
const int x = i + dirs[k];
const int y = j + dirs[k + 1];
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (board[x][y] != 'O')
continue;
q.emplace(x, y);
board[x][y] = '*';
}
}

for (vector<char>& row : board)
for (char& c : row)
if (c == '*')
c = 'O';
else if (c == 'O')
c = 'X';
}
};```

### Surrounded Regions Leetcode Solution in Java

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

final int m = board.length;
final int n = board[0].length;
final int[] dirs = {0, 1, 0, -1, 0};
Queue<int[]> q = new ArrayDeque<>();

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (i * j == 0 || i == m - 1 || j == n - 1)
if (board[i][j] == 'O') {
q.offer(new int[] {i, j});
board[i][j] = '*';
}

// Mark grids that stretch from four sides with '*'
while (!q.isEmpty()) {
final int i = q.peek()[0];
final int j = q.poll()[1];
for (int k = 0; k < 4; ++k) {
final int x = i + dirs[k];
final int y = j + dirs[k + 1];
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (board[x][y] != 'O')
continue;
q.offer(new int[] {x, y});
board[x][y] = '*';
}
}

for (char[] row : board)
for (int i = 0; i < row.length; ++i)
if (row[i] == '*')
row[i] = 'O';
else if (row[i] == 'O')
row[i] = 'X';
}
}```

Note: This problem Surrounded Regions is generated by Leetcode but the solution is provided by Chase2learn This tutorial is only for Educational and Learning purpose.

Sharing Is Caring