LeetCode: Surrounded Regions

## https://code.dennyzhang.com/surrounded-regions
## Basic Ideas: Graph
##
##    First pass: Do dfs/bfs from the boarders, to keep 0s
##    Second pass: change values
##
## Complexity: Time O(n*m), Space O(1)
class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if not board: return
        n, m = len(board), len(board[0])
        def dfs(i, j):
            if i<0 or i>=n or j<0 or j>=m:
                return
            if board[i][j] != "O":
                return
            # Change 0 to 1 as visited
            board[i][j] = "1"
            dfs(i+1, j)
            dfs(i-1, j)
            dfs(i, j+1)
            dfs(i, j-1)
        # graph traverse from boarders
        boarders = []
        for k in range(max(n, m)):
            boarders += [(0,k), (n-1,k), (k, 0), (k, m-1)]

        for i, j in boarders:
            dfs(i, j)

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