被围绕的区域

[编程题]被围绕的区域

热度指数：2246 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个 n*m 大小的的矩阵，矩阵中由 ‘X' 和 'O' 构成，找到所有被 'X' 围绕的区域，并将其用 'X' 填充。

例如：

[['X','X','X','X'],

['X','O','O','X'],

['X','O','X','X'],

['X','X','O','X']]

中间的三个 ‘O’ 被 'X'围绕，因此将其填充为 'X' ，但第四行的 'O' 下方没有被 'X' 围绕，因此不改变，结果为

[['X','X','X','X'],

['X','X','X','X'],

['X','X','O','X']]

数据范围： $1 \le n , m \le 200 \$ ，矩阵中保证只含有 'X' 和 'O'

示例1

输入

[[X,X,X,X],[X,O,O,X],[X,O,X,X],[X,X,O,X]]

输出

[[X,X,X,X],[X,X,X,X],[X,X,X,X],[X,X,O,X]]

示例2

输入

[[O]]

输出

[[O]]

备注:

算法知识视频讲解

mmm久念

发表于 2022-01-11 12:54:54

【NC226 被围绕的区域】 DFS做法（java）思路用题目给的例子说明：一开始是这样的矩阵： [['X','X','X','X'], ['X','O','O','X'], ['X','O','X','X'], ['X','X','O','X']] 最外面那圈的'O'不会被围住，所以先把展开全文

牛客768685351号

发表于 2022-03-12 20:20:42

解决思路很妙：对边界进行dfs，以边界为起点，搜索到的O都不应该被替换成X，其他的O都可以被替换成X class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * 展开全文

小菲柱

发表于 2022-07-28 22:29:09

想做并查集的，结果dfs更容易 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param board char字符型vector<vec 展开全文

指向不明的野指针

发表于 2022-05-09 20:20:45

由于不想用dfs写，就想了个别的。这里使用类似于并查集的思想，首先将原本O的位置置位X，并且对于所有O的位置进行记录。记录完毕后对board周围的元素先进行复原，然后从先从左上角开始根据O的记录表参考逐一复原O，然后在从右下角开始往左上角开始逐一复原（矩形对称性）。 class Solution 展开全文

fred-coder

发表于 2022-01-11 13:27:04

dfs, 由于和边界值上的"O"相连的都不能被修改,先对边界值相邻的"O"进行状态调整,再修改符合条件的 "O" 的值 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param board char字符型二维数组 # @return char字符展开全文