0130. 被围绕的区域 #
- 标签:深度优先搜索、广度优先搜索、并查集、数组、矩阵
- 难度:中等
题目大意 #
描述:给定一个 m * n
的矩阵 board
,由若干字符 X
和 O
构成。
要求:找到所有被 X
围绕的区域,并将这些区域里所有的 O
用 X
填充。
说明:
- $m == board.length$。
- $n == board[i].length$。
- $1 <= m, n <= 200$。
- $board[i][j]$ 为
'X'
或'O'
。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 1:深度优先搜索 #
根据题意,任何边界上的 O
都不会被填充为X
。而被填充 X
的 O
一定在内部不在边界上。
所以我们可以用深度优先搜索先搜索边界上的 O
以及与边界相连的 O
,将其先标记为 #
。
最后遍历一遍 board
,将所有 #
变换为 O
,将所有 O
变换为 X
。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n \times m)$,其中 $m$ 和 $n$ 分别为行数和列数。
- 空间复杂度:$O(n \times m)$。