# Leetcode 130. Surrounded Regions

## 題解

### DFS

透過標記聯通邊界的 O 為 # 來判斷

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        m,n = len(board),len(board[0])

        directions = [
            [0,1],[1,0],[0,-1],[-1,0]
        ]

        def dfs(x,y):
            if x < 0 or x >= n or y < 0 or y >= m or board[y][x] != "O":
                return
            board[y][x] = "#"
            for direction in directions:
                new_x = x + direction[0]
                new_y = y + direction[1]
                dfs(new_x,new_y)

        # 標記聯通邊界的 O
        for y in range(m):
            for x in range(n):
                if x == 0 or x == n - 1 or y == 0 or y == m - 1:
                    dfs(x,y)
        
        for y in range(m):
            for x in range(n):
                if board[y][x] == "#":
                    board[y][x] = "O"
                elif board[y][x] == "O":
                    board[y][x] = "X"