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.lengthn == board[i].length1 <= m, n <= 200board[i][j]is'X'or'O'.
Now, let’s 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 Solution in 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.
