「力扣」第 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’ 改为 ‘-‘ 这个问题。


文章作者: liweiwei1419
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 liweiwei1419 !
评论
 上一篇
「力扣」第 131 题:分割回文串 「力扣」第 131 题:分割回文串
「力扣」第 131 题:分割回文串 链接 题解链接 给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。返回 s 所有可能的分割方案。 示例: 输入: "aab" 输出: [ ["aa&quo
下一篇 
「力扣」第 93 题:复原 IP 地址(中等) 「力扣」第 93 题:复原 IP 地址(中等)
「力扣」第 93 题:复原 IP 地址(中等) 链接 题解链接 给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。 示例: 输入: "25525511135" 输出: ["255.25
  目录