130.Surrounded-Regions.md

130. Surrounded Regions

Difficulty: Medium

URL

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

Solution

Approach 1: DFS

The code is shown below:

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        row, col = len(board), len(board[0])
        
        def dfs(i, j):
            nonlocal row, col, board
            if i < 0 or i >= row or j < 0 or j >= col:
                return
            if board[i][j] != 'O':
                return
            board[i][j] = '#'
            dfs(i-1, j)
            dfs(i+1, j)
            dfs(i, j+1)
            dfs(i, j-1)
            return

        for r in range(row):
            if board[r][0] == 'O':
                dfs(r, 0)
                board[r][0] == '#'
            if board[r][col-1] == 'O':
                dfs(r, col-1)
                board[r][col-1] == '#'
        for c in range(col):
            if board[0][c] == 'O':
                dfs(0, c)
                board[0][c] == '#'
            if board[row-1][c] == 'O':
                dfs(row-1, c)
                board[row-1][c] == '#'
        
        for r in range(row):
            for c in range(col):
                if board[r][c] == 'O':
                    board[r][c] = 'X'
                elif board[r][c] == '#':
                    board[r][c] = 'O'