Surrounded Regions

Problem

https://leetcode.com/problems/surrounded-regions/

You are given an m x n matrix board containing letters 'X' and 'O', capture regions that are surrounded:

• Connect: A cell is connected to adjacent cells horizontally or vertically.

• Region: To form a region connect every 'O' cell.

• Surround: The region is surrounded with 'X' cells if you can connect the region with 'X' cells and none of the region cells are on the edge of the board.

A surrounded region is captured by replacing all 'O's with 'X's in the input matrix board.

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"]]

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

Pattern

Graph, DFS, Matrix

Approaches

DFS

Code

def solve(board: list[list[str]]) -> None:
    """Capture surrounded regions in-place."""
    m = len(board)
    n = len(board[0])

    def dfs(i: int, j: int) -> None:
        if not (0 <= i < m and 0 <= j < n):
            return
        if board[i][j] != "O":
            return
        board[i][j] = "S"
        dfs(i + 1, j)
        dfs(i - 1, j)
        dfs(i, j - 1)
        dfs(i, j + 1)

    for i in range(m):
        dfs(i, 0)
        dfs(i, n - 1)

    for j in range(n):
        dfs(0, j)
        dfs(m - 1, j)

    for i in range(m):
        for j in range(n):
            if board[i][j] == "O":
                board[i][j] = "X"
            if board[i][j] == "S":
                board[i][j] = "O"

Test

>>> from surrounded_regions__dfs import solve
>>> board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
>>> solve(board)
>>> board
[['X', 'X', 'X', 'X'], ['X', 'X', 'X', 'X'], ['X', 'X', 'X', 'X'], ['X', 'O', 'X', 'X']]
>>> board = [["X"]]
>>> solve(board)
>>> board
[['X']]

surrounded_regions__dfs.solve(board: list[list[str]]) → None

Capture surrounded regions in-place.