LeetCode: 130 Surrounded Regions

Given an m x n matrix board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

Example:

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"]
]

Explanation:

Surrounded regions should not be on the border, which means that any `'O'` on the border cannot be flipped to `'X'`. Any `'O'` that is connected to an `'O'` on the border will not be flipped to `'X'`. The other `'O'`s are flipped to `'X'`.

问题

给定一个 m x n 的矩阵 board，其中包含 'X' 和 'O'，捕获所有被 'X' 围绕的区域。

被围绕的区域通过将该区域内所有 'O' 翻转为 'X' 来捕获。

解决方案

深度优先搜索 (DFS) 和广度优先搜索 (BFS)

Approach: Mark and Flip Using DFS/BFS / 标记和翻转法

This approach involves marking all 'O's that are connected to the border (since they cannot be surrounded) and then flipping the remaining 'O's to 'X'. We traverse the grid starting from the borders and use DFS or BFS to mark the safe 'O's.

这种方法涉及标记与边界相连的所有 'O'（因为它们无法被包围），然后将剩下的 'O' 翻转为 'X'。我们从边界开始遍历网格，使用 DFS 或 BFS 标记安全的 'O'。

Implementation / 实现

Python

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

        rows, cols = len(board), len(board[0])

        def dfs(r, c):
            if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != 'O':
                return
            board[r][c] = 'T'  # Temporarily mark as 'T'
            dfs(r - 1, c)
            dfs(r + 1, c)
            dfs(r, c - 1)
            dfs(r, c + 1)

        # Mark the 'O's on the borders and their connected components
        for r in range(rows):
            dfs(r, 0)
            dfs(r, cols - 1)
        for c in range(cols):
            dfs(0, c)
            dfs(rows - 1, c)

        # Flip the remaining 'O's to 'X' and revert 'T' to 'O'
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == 'O':
                    board[r][c] = 'X'
                elif board[r][c] == 'T':
                    board[r][c] = 'O'

Explanation / 解释

Check for Empty Board / 检查空板
```
if not board:
   return
```
- English: If the board is empty, we return immediately as there’s nothing to process.
- Chinese: 如果棋盘为空，我们立即返回，因为没有需要处理的内容。
DFS Function for Marking / 标记的 DFS 函数
```
def dfs(r, c):
   if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != 'O':
       return
   board[r][c] = 'T'  # Temporarily mark as 'T'
   dfs(r - 1, c)
   dfs(r + 1, c)
   dfs(r, c - 1)
   dfs(r, c + 1)
```
- English: The dfs function marks all 'O's connected to the current cell as 'T' to indicate they are safe and should not be flipped.
- Chinese: dfs 函数将与当前单元格相连的所有 'O' 标记为 'T'，表示它们是安全的，不应被翻转。
Mark Border-Connected 'O's / 标记与边界相连的 'O'
```
for r in range(rows):
   dfs(r, 0)
   dfs(r, cols - 1)
for c in range(cols):
   dfs(0, c)
   dfs(rows - 1, c)
```
- English: We apply the DFS function on the border cells and their connected 'O's to mark them as 'T'.
- Chinese: 我们对边界单元格及其相连的 'O' 应用 DFS 函数，将它们标记为 'T'。
Flip and Revert / 翻转和还原
```
for r in range(rows):
   for c in range(cols):
       if board[r][c] == 'O':
           board[r][c] = 'X'
       elif board[r][c] == 'T':
           board[r][c] = 'O'
```
- English: Finally, we flip all remaining 'O's to 'X' (since they are surrounded) and revert the 'T's back to 'O'.
- Chinese: 最后，我们将所有剩余的 'O' 翻转为 'X'（因为它们被包围），并将 'T' 还原为 'O'。

Alternative BFS Implementation / BFS 实现

BFS can be used instead of DFS to mark the border-connected 'O's. The approach is similar but uses a queue to manage the exploration.

可以使用 BFS 代替 DFS 来标记与边界相连的 'O'。该方法类似，但使用队列来管理探索。

BFS Implementation / BFS 实现

from collections import deque

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

        rows, cols = len(board), len(board[0])

        def bfs(r, c):
            queue = deque([(r, c)])
            while queue:
                x, y = queue.popleft()
                if x < 0 or x >= rows or y < 0 or y >= cols or board[x][y] != 'O':
                    continue
                board[x][y] = 'T'
                queue.append((x - 1, y))
                queue.append((x + 1, y))
                queue.append((x, y - 1))
                queue.append((x, y + 1))

        # Mark the 'O's on the borders and their connected components
        for r in range(rows):
            bfs(r, 0)
            bfs(r, cols - 1)
        for c in range(cols):
            bfs(0, c)
            bfs(rows - 1, c)

        # Flip the remaining 'O's to 'X' and revert 'T' to 'O'
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == 'O':
                    board[r][c] = 'X'
                elif board[r][c] == 'T':
                    board[r][c] = 'O'

Complexity Analysis / 复杂度分析

Time Complexity / 时间复杂度: O(m * n), where m is the number of rows and n is the number of columns. We potentially visit every cell once.
Space Complexity / 空间复杂度: O(m * n) in the worst case for the BFS queue or DFS recursion stack.

Key Concept / 关键概念

Mark and Flip / 标记和翻转: This technique ensures that only the 'O's that are fully surrounded are flipped, by first marking the 'O's connected to the border as safe.
标记和翻转: 这种技术通过首先标记与边界相连的 'O' 为安全，确保只有完全被包围的 'O' 被翻转。

Summary / 总结

English: The Mark and Flip method, implemented with either DFS or BFS, is effective for solving problems where certain regions of a grid need to be preserved while others are modified.
Chinese: 标记和翻转方法，使用 DFS 或 BFS 实现，对于解决需要保留网格某些区域而修改其他区域的问题非常有效。

Tips / 提示

English: Practice using both DFS and BFS to explore and manipulate grids, as these techniques are widely applicable in grid-based problems.
Chinese: 练习使用 DFS 和 BFS 来探索和操作网格，因为这些技术在基于网格的问题中广泛适用。

Solution Template for Similar Questions / 提示

English: Use DFS or BFS whenever you need to explore connected regions in a grid, especially when some regions need to be preserved or marked.
Chinese: 每当你需要在网格中探索连接区域时，特别是当某些区域需要保留或标记时，使用 DFS 或 BFS。

5 More Similar Questions / 推荐5问题

Recommended Resources / 推荐资源

English: Practice problems that involve exploring and manipulating grids using DFS or BFS to strengthen your understanding of these traversal techniques.
Chinese: 练习涉及使用 DFS 或 BFS 探索和操作网格的问题，以加强你对这些遍历技术的理解。

Surrounded Regions – Graph – Leetcode 130 – Python by Neetcode

Post Views: 48

CODEBITWAVE