130. Surrounded Regions

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

solution

• bfs

时间复杂度：O() 空间复杂度：O()

• dfs

class Solution:
    def __init__(self):
        self.dirs = [[1, 0], [-1, 0], [0, -1], [0, 1]]
    
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        m = len(board)
        n = len(board[0])
        visited = [[False] * n for _ in range(m)]
        for i in range(m):
            if board[i][0] == 'O' and not visited[i][0]:
                self.dfs(board, i, 0, visited)
            if board[i][n-1] == 'O' and not visited[i][n-1]:
                self.dfs(board, i, n-1, visited)

        for j in range(n):
            if board[0][j] == 'O' and not visited[0][j]:
                self.dfs(board, 0, j, visited)
            if board[m-1][j] == 'O' and not visited[m-1][j]:
                self.dfs(board, m-1, j, visited)
        
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                elif board[i][j] == 'A':
                    board[i][j] = 'O'       
        
        return board
    
    def dfs(self, board, i, j, visited):
        if visited[i][j] or board[i][j] == "X":
            return
        
        board[i][j] = 'A'
        visited[i][j] = True

        for dir in self.dirs:
            new_i = i + dir[0]
            new_j = j + dir[1]
            if new_i < 0 or new_i >= len(board) or new_j < 0 or new_j >= len(board[0]):                
                continue

            self.dfs(board, new_i, new_j, visited)

时间复杂度：O() 空间复杂度：O()