Leetcode Surrounded Regions problem solution

In this Leetcode Surrounded Regions problem solution we have Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.

Problem solution in Python.

```class Solution:
def solve(self, board: List[List[str]]) -> None:
point_set = set()

def outside_border(i, j):
if (i == 0 or i == len(board) - 1) or (j == 0 or j == len(board[i]) - 1):
return True
return False

def dfs(i, j):
directions = [(0, 1), (1, 0), (-1, 0), (0, -1)]
for direction in directions:
new_x = i + direction[0]
new_y = j + direction[1]
if (0 <= new_x < len(board) and 0 <= new_y < len(board[i]) and board[new_x][new_y] == 'O'
and (new_x, new_y) not in point_set):
dfs(new_x, new_y)

for i in range(len(board)):
for j in range(len(board[i])):
if board[i][j] == 'O' and outside_border(i, j):
dfs(i, j)

for i in range(len(board)):
for j in range(len(board[i])):
if board[i][j] == 'O' and (i , j) not in point_set:
board[i][j] = 'X'
```

Problem solution in Java.

```class Solution {
public void solve(char[][] board) {
if (board.length == 1 || board[0].length == 1) return;
for (int i = 0; i < board[0].length; i++) {
if (board[0][i] == 'O') visit(board, 0, i);
if (board[board.length - 1][i] == 'O') visit(board, board.length - 1, i);
}
for (int i = 1; i < board.length - 1; i++) {
if (board[i][0] == 'O') visit(board, i, 0);
if (board[i][board[0].length - 1] == 'O') visit(board, i, board[0].length - 1);
}
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == 'Y') board[i][j] = 'O';
else board[i][j] = 'X';
}
}
}

private void visit(char[][] board, int i, int j) {
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != 'O') return;
board[i][j] = 'Y';
visit(board, i - 1, j);
visit(board, i + 1, j);
visit(board, i, j - 1);
visit(board, i, j + 1);
}
}
```

Problem solution in C++.

```class Solution {
int rows,cols;
vector<vector<bool>> vis;
void dfs(vector<vector<char>>& board,int i,int j)
{
if(i<0||i>=rows||j<0||j>=cols||board[i][j]=='X'||vis[i][j]) return;
vis[i][j]=true;
dfs(board,i-1,j);
dfs(board,i+1,j);
dfs(board,i,j-1);
dfs(board,i,j+1);
return;
}
public:
void solve(vector<vector<char>>& board) {
if(board.empty()) return;
rows=board.size();
cols=board[0].size();

vis.resize(rows,vector<bool>(cols,false));

for(int i=0;i<rows;i++)
{
for(int j=0;j<cols;j++)
{
if((i==0||i==rows-1||j==0||j==cols-1)&&(board[i][j]=='O'))
dfs(board,i,j);
}
}

for(int i=0;i<rows;i++)
{
for(int j=0;j<cols;j++)
{
if(!vis[i][j]&&board[i][j]=='O')
{
vis[i][j]=true;
board[i][j]='X';
}
}
}

return;

}
};
```

Problem solution in C.

```void dfs(char **board, int i, int j, int row_sz, int col_sz)
{

if('X' == board[i][j])
{
return;
}

if('K' == board[i][j])
{
return;
}
board[i][j] = 'K';

if(j-1 > 0)
dfs(board, i, j-1, row_sz, col_sz);
if(j+1 < col_sz)
dfs(board, i, j+1, row_sz, col_sz);
if(i-1 > 0)
dfs(board, i-1, j, row_sz, col_sz);
if(i+1 < row_sz)
dfs(board, i+1, j, row_sz, col_sz);
}

void solve(char** board, int boardSize, int* boardColSize){

if(NULL == board) return;
if((boardSize <= 1) || (*boardColSize <= 1)) return;

int row_sz = boardSize;
int col_sz = *boardColSize;

int i,j;

for(j=0;j<col_sz;j++)
{
if(board[0][j] == 'O') dfs(board, 0, j, row_sz, col_sz);
}

for(i=0;i<row_sz;i++)
{
if(board[i][col_sz - 1] == 'O')
dfs(board, i, col_sz - 1, row_sz, col_sz);
}

for(j=0;j<col_sz;j++)
{
if(board[row_sz-1][j] == 'O')
dfs(board, row_sz - 1, j, row_sz, col_sz);
}

for(i=0;i<row_sz;i++)
{
if(board[i][0] == 'O')
dfs(board, i, 0, row_sz, col_sz);
}

for(i=0;i<row_sz;i++)
{
for(j=0;j<col_sz;j++)
{
if(board[i][j] == 'K') board[i][j] = 'O';
else board[i][j] = 'X';
}
}

}
```