The surrounded regions problem in Python

Problem statement

This problem is based on finding regions in our binary 2D matrix surrounded by other elements. The elements are donated by X and O. We need to replace the O with X if other elements surround them. A cell is considered to be surrounded if either of these two conditions are met:

All its surrounding cells are X.
The surrounding cells are out of the bound of the matrix.

An example of this is given below:

def solve(board):
    rows = len(board)
    columns = len(board[0])
    for col in range(columns):
        dfs(board, 0, col, rows, columns)
        dfs(board, rows - 1, col, rows, columns)
    for row in range(rows):
        dfs(board, row, 0, rows, columns)
        dfs(board, row, columns - 1, rows, columns)
    for row in range(rows):
        for col in range(columns):
            if board[row][col] == 'O':
                board[row][col] = 'X'
            elif board[row][col] == 'V':
                board[row][col] = 'O'
def dfs(board, row, col, rows, columns):
    if row < 0 or row >= rows or col < 0 or col >= columns or board[row][col] != 'O':
        return
    board[row][col] = 'V'
    dfs(board, row - 1, col, rows, columns)
    dfs(board, row + 1, col, rows, columns)
    dfs(board, row, col - 1, rows, columns)
    dfs(board, row, col + 1, rows, columns)

Explanation

The code is explained below:

Line 1: This is the definition of the solve function, which takes the 2D board as a parameter.
Lines 2–3: We retrieve the size of the rows and columns of the board matrix.
Lines 5–7: We iterate over the cells in the first and last rows of the matrix. Mark each visited cell with O as V to indicate that it has been visited during the DFS process.
Lines 9–11: Similarly, we iterate over the cells in the first and last columns of the matrix and mark each visited cell with O as V.
Lines 13–18: We iterate over every cell in the matrix. If the cell contains O, it means it is part of a surrounding region and should be changed to X. If the cell contains V, it means it was visited during the DFS process and should be restored to O because it is not surrounded.
Lines 20–29: The dfs function takes two parameters, row and col, representing the current cell in the matrix. It checks if the current cell is within the bounds of the matrix and if it is a O cell. If these conditions are met, it marks the current cell as V to indicate it has been visited. It then recursively calls itself on the neighboring cells (up, down, left, right) to continue the DFS process.

The surrounded regions problem in Python

Problem statement

Solution

Explanation