題目連結: 130. Surrounded Regions

題目描述:給你一個 m x n 的矩陣 board，由 'X' 和 'O' 組成。請你找出所有被 'X' 完全圍住的 'O' 區域，並將它們翻轉成 'X'。

Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]

Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]

Python

解題思路:
如果我們試圖去找出「被圍住的 O」，邏輯會很複雜。對於一片 'O'，你需要檢查它所有路徑的盡頭是不是都是 'X'。
我們反過來想，在邊界上的O是不可能被圍住的。
流程步驟是:
1.找出所有「安全的 O」，給它們一個臨時的特殊標記（例如 'S')
2.掃描整個棋盤，將所有剩下的 'O'（它們都是被圍住的）翻轉成 'X'
3.所有被標記為 'S' 的格子恢復成 'O'。

下面程式碼用DFS方法來做介紹。

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

        def dfs(row,col):
            if 0<=row<rows and 0<=col<cols and board[row][col]=='O':
                board[row][col] = 'S'
                dfs(row+1,col)
                dfs(row-1,col)
                dfs(row,col+1)
                dfs(row,col-1)
            return
        for c in range(cols):
            if board[0][c] == 'O':
                dfs(0,c)
            if board[rows-1][c] == 'O':
                dfs(rows-1,c)
        
        for r in range(rows):
            if board[r][0] =='O':
                dfs(r,0)
            if board[r][cols-1] =='O':
                dfs(r,cols-1)
        
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == 'O':
                    board[r][c] = 'X'
                elif board[r][c] == 'S':
                    board[r][c] = 'O'

演算法分析:

• dfs函式的意思是 如果當前的位置沒有超過範圍且是'O'時，就改成'S'且遞迴當前位置的上下左右。
• 第一個雙層迴圈先檢查第一行(row)與最後一行為'O'的值然後標記起來(因為他們是安全的)。
• 第二個雙層迴圈先檢查第一列(col)與最後一列為'O'的值，方法同上。
• X X X X
  X O O X
  X X O X
  X O X X 當掃描到最後一行的O會改變成S
• X X X X
  X O O X
  X X O X
  X S X X接著尋找與S相連的'O'也同樣標記
• 最後探索完畢，執行最後一個雙層迴圈，將剩下被圍住的'O'都改成'X'，接著剩下安全的標記就可以改回'O'了。

複雜度分析:

• 時間複雜度為 O(m * n)。

• 空間複雜度： O(m * n) (空間消耗主要來自於遞迴呼叫的堆疊)。

這題最重要的是逆向思考，用這種方法解這道題會比較簡單一些。
這樣有對圖論題型有更加了解了嗎
有問題可以底下留言!
下回見!!