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.lengthn == board[i].length1 <= m, n <= 200board[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>;
}
};
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"]]
#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++) {
borders.add(Arrays.asList(r, 0));
borders.add(Arrays.asList(r, cols - 1));
}
for (int c = 0; c < cols; c++) {
borders.add(Arrays.asList(0, c));
borders.add(Arrays.asList(rows - 1, 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);
}
}
}
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"]]
#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);
}
Input
board = [["X"]]
Output
[["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"
Input
board = [["X"]]
Output
[["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]++;
}
}
}
}
}
Input
board = [["X"]]
Output
[["X"]]