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, 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.