How does Depth-First Search help in solving Surrounded Regions?

DFS helps by marking all 'O's connected to the border as safe, ensuring only enclosed regions are changed. This makes traversal efficient while ensuring the correctness of the result.

What happens if I don't handle border 'O's correctly?

If border 'O's are not correctly identified and marked, surrounded regions might not be transformed, leading to an incorrect solution.

What are the trade-offs between DFS, BFS, and Union-Find for this problem?

DFS is straightforward but risks stack overflow for large boards. BFS is iterative and avoids this risk. Union-Find offers a more complex but highly efficient solution for union and find operations.

How does the board's size impact the solution's efficiency?

The size of the board impacts both time and space complexity. Larger boards require more memory and processing time, especially for recursive DFS or BFS operations.

Can you explain the time complexity of the solution?

The time complexity of both DFS and BFS is O(m*n), where m and n are the dimensions of the board. Every cell is visited at most once, making this a linear traversal.

#130

Medium

auto_awesome图·搜索

LeetCode 题解工作台

被围绕的区域

给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' 组成，捕获所有被围绕的区域：连接：一个单元格与水平或垂直方向上相邻的单元格连接。区域：连接所有 'O' 的单元格来形成一个区域。围绕：如果一个区域中的所有 'O' 单元格都不在棋盘的边缘，则该区域被包围。这…

数组深度优先搜索广度优先搜索并查集矩阵

题目描述

给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' 组成，捕获所有 被围绕的区域：

连接：一个单元格与水平或垂直方向上相邻的单元格连接。
区域：连接所有 'O' 的单元格来形成一个区域。
围绕：如果一个区域中的所有 'O' 单元格都不在棋盘的边缘，则该区域被包围。这样的区域完全被 'X' 单元格包围。

通过原地将输入矩阵中的所有 'O' 替换为 'X' 来 捕获被围绕的区域。你不需要返回任何值。

示例 1：

输入：board = [['X','X','X','X'],['X','O','O','X'],['X','X','O','X'],['X','O','X','X']]

输出：[['X','X','X','X'],['X','X','X','X'],['X','X','X','X'],['X','O','X','X']]

解释：

在上图中，底部的区域没有被捕获，因为它在 board 的边缘并且不能被围绕。

示例 2：

输入：board = [['X']]

输出：[['X']]

提示：

m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] 为 'X' 或 'O'

lightbulb

解题思路

方法一：DFS

我们可以从矩阵的边界开始，将矩阵边界上的每个 O 作为起始点，开始进行深度优先搜索。将搜索到的 O 全部替换成 .。

然后我们再遍历这个矩阵，对于每个位置：

如果是 .，则替换成 O；
否则如果是 O，则替换成 X。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        def dfs(i: int, j: int):
            if not (0 <= i < m and 0 <= j < n and board[i][j] == "O"):
                return
            board[i][j] = "."
            for a, b in pairwise((-1, 0, 1, 0, -1)):
                dfs(i + a, j + b)

        m, n = len(board), len(board[0])
        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] == ".":
                    board[i][j] = "O"
                elif board[i][j] == "O":
                    board[i][j] = "X"

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Do you understand how Depth-First Search can be applied to matrix traversal?
question_mark
Can you optimize the solution to handle the largest board sizes efficiently?
question_mark
Will you be able to explain how BFS or Union-Find compares to DFS in solving this problem?

warning

常见陷阱

外企场景

error
Failing to properly mark border 'O's as safe, leading to incorrect regions being transformed.
error
Not managing the traversal stack or queue efficiently, causing stack overflow or excessive memory use for large boards.
error
Overlooking edge cases like small boards (1x1), single row/column, or when there are no surrounded regions at all.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the board size is extremely large, say up to 1000x1000? How would you approach optimizing the solution?
arrow_right_alt
Can you solve the problem using an iterative DFS approach to avoid recursion limits in Python?
arrow_right_alt
How would you modify the solution if 'O's could be adjacent diagonally instead of only horizontally/vertically?

help

常见问题

外企场景

继续练习

#200 岛屿数量 #695 岛屿的最大面积 #778 水位上升的泳池中游泳