#130

Surrounded Regions

medium· Graphsruns: 0

Given an m x n matrix board containing 'X' and 'O', capture all regions of 'O' that are 4-directionally surrounded by 'X'. A region is captured by flipping all 'O' in it to 'X'. Regions connected to the border are not captured.

wpm 0acc 100%time 0:000 / 873

class Solution:
    def solve(self, board: list[list[str]]) -> None:
        rows, cols = len(board), len(board[0])

        def dfs(r: int, c: int) -> None:
            if (
                r < 0
                or r >= rows
                or c < 0
                or c >= cols
                or board[r][c] != "O"
            ):
                return
            board[r][c] = "S"
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)

        for r in range(rows):
            dfs(r, 0)
            dfs(r, cols - 1)
        for c in range(cols):
            dfs(0, c)
            dfs(rows - 1, c)
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == "O":
                    board[r][c] = "X"
                elif board[r][c] == "S":
                    board[r][c] = "O"

click the box to focus · tab inserts 4 spaces · backspace to correct · esc to pause

desktop only

codedrill is a typing game and needs a real keyboard. open this on a laptop or desktop to practice.

you can still browse problems and sections from your phone.