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
- A region is captured unless it touches the border. So identify all
'O'cells connected to the border, and mark them as safe. - Flood-fill from every border
'O'with a temporary marker. - Then sweep the board: remaining
'O'cells are enclosed (turn them to'X'), and markers revert to'O'. - 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.