「力扣」第 130 题:被围绕的区域
- 链接:130. 被围绕的区域。
给定一个二维的矩阵,包含
'X'
和'O'
(字母 O)。找到所有被
'X'
围绕的区域,并将这些区域里所有的'O'
用'X'
填充。示例:
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
解释:
被围绕的区间不会存在于边界上,换句话说,任何边界上的
'O'
都不会被填充为'X'
。 任何不在边界上,或不与边界上的'O'
相连的'O'
最终都会被填充为'X'
。如果两个元素在水平或垂直方向相邻,则称它们是“相连”的。
分析:因为不涉及到最少步或者最优解问题。 这道题可以有很多解法 BFS、DFS、UNION FIND。
思路:不要想着怎么把连通区域找到,反而是想怎么把连通边界找到。
首先对边界上每一个 ‘O’ 做深度优先搜索,将与其相连的所有 ‘O’ 改为 ‘-‘ 。然后遍历矩阵,将矩阵中所有 ‘O’ 改为 ‘X’ ,将矩阵中所有 ‘-‘ 变为 ‘O’。
于是问题就转换成了如何将边界上与最开始的 ‘O’ 改为 ‘-‘ 这个问题。