130. Surrounded Regions

Question: Surrounded Regions

Solution

想法：

1. 先把沒有被 X 包圍的 O 挑出來
   • O 會在 board 的外圍
     1. r = 0, c = 0, 1, 2, … columns - 1
     2. r = rows - 1, c = 0, 1, 2, …. columns - 1
     3. c = 0, r = 0, 1, 2,.. rows - 1
     4. c = columns - 1, r = 0, 1, 2, …. rows - 1
   • 如果外圍有 O， dfs 往內找相鄰也為 O
   • 這些 O 都先標記成 T，最後再變回 O
2. 把沒有標記成 T 的 O 都變成 X
3. 把標記成 T 的都變成 O

class Solution(object):
    def solve(self, board):
        """
        :type board: List[List[str]]
        :rtype: None Do not return anything, modify board in-place instead.
        """
        rows, columns = len(board), len(board[0])
        
        visited = set()
        def dfs(r, c):
            if (
                r < 0 or
                c < 0 or
                r > rows - 1 or
                c > columns - 1 or
                (r, c) in visited or
                board[r][c] == "X"
            ):
                return 
            visited.add((r, c))
            board[r][c] = "T"
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)
        # 1. DFS capture unsurrounding regions (O -> T)
        for c in range(columns):
            if board[0][c] == "O":
                dfs(0, c)
            if board[rows - 1][c] == "O":
                dfs(rows - 1, c)
        for r in range(1, rows):
            if board[r][0] == "O":
                dfs(r, 0)
            if board[r][columns - 1] == "O":
                dfs(r, columns - 1)
        
        # 2. capture surrounding regions (O -> X)
        for r in range(rows):
            for c in range(columns):
                if board[r][c] == "O":
                    board[r][c] = "X"
                # 3. uncapture unsurrounding regions (O -> T)
                elif board[r][c] == "T":
                    board[r][c] = "O"
        return board

Video Solution