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

Leetcode Surrounded Regions problem solution


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):
            point_set.add((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';
     	}
    }
    
}