[LeetCode] 130. Surrounded Regions

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

Use DFS approach to traverse from 4 edges of the given board.  Replace every visited  'O' with '#'.

Iterate each rows to replace every 'O' with 'X' and every '#' with 'O'

Time Complexity = O ( M * N ),   M = total rows of board,  N = total columns of board.

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        
        if not board:
            return
        
        row = len(board)
        column = len(board[0])
        
        def dfs(y, x):
            if board[y][x] == 'X' or board[y][x] == '#':
                return
            
            board[y][x] = '#'
            
            for dy in (-1, 1):
                if 0 <= y + dy < row:
                    dfs(y + dy, x)
          
            for dx in (-1, 1):
                if 0 <= x + dx < column:
                    dfs(y, x + dx)
        
        for i in range(row):
            for j in (0, column - 1):
                dfs(i, j)
        
        for i in (0, row -1):
            for j in range(column):
                dfs(i, j)
                
        
        for i in range(row):
            for j in range(column):
                if board[i][j] == '#':
                    board[i][j] = 'O'
                else:
                    board[i][j] = 'X'