⚡Flashcard Drill➔
NeetCode #570LC-130MediumGraphsNC 150NC 250
← Back to All Problems

#570 · #130 · Surrounded Regions(被围绕的区域)

📌 Problem Statement & Constraints

Given an m x n board of 'X' and 'O', capture all regions of 'O' that are completely surrounded by 'X' by turning them into 'X'. 'O' cells on the border are not captured. Constraints: 1 <= m, n <= 200.

💡 Core Algorithmic Approaches

  1. A region is captured unless it touches the border. So identify all 'O' cells connected to the border, and mark them as safe.
  2. Flood-fill from every border 'O' with a temporary marker.
  3. Then sweep the board: remaining 'O' cells are enclosed (turn them to 'X'), and markers revert to 'O'.
  4. The reverse-reachability trick avoids checking each region for a border contact.

💻 Benchmark Python3 Implementation

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        if not board:
            return
        m, n = len(board), len(board[0])

        def dfs(r: int, c: int) -> None:
            if not (0 <= r < m and 0 <= c < n) or board[r][c] != "O":
                return
            board[r][c] = "S"              # temporarily mark as safe
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)

        # mark everything connected to a border
        for i in range(m):
            dfs(i, 0)
            dfs(i, n - 1)
        for j in range(n):
            dfs(0, j)
            dfs(m - 1, j)

        for i in range(m):
            for j in range(n):
                if board[i][j] == "O":
                    board[i][j] = "X"      # enclosed -> captured
                elif board[i][j] == "S":
                    board[i][j] = "O"      # restore the safe cells

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n): each cell is visited a constant number of times.
💾 Space Complexity
O(m * n) for the recursion stack in the worst case.

⚠️ Interview Pitfalls & Follow-ups

  • Checking each 'O' region for a border contact: workable but requires tracking regions; the border flood-fill is simpler.
  • Using a marker that collides with the board characters: 'S' is safe for an 'X'/'O' board.
  • Forgetting to restore the markers: the safe cells must become 'O' again.
  • Recursing on a 200x200 all-'O' board: the depth can reach 40 000; an iterative BFS is safer.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems