备考首页> 数据结构> 数组
42

编程题 42 /92

现在有一个仅包含‘X’和‘O’的二维板，请捕获所有的被‘X’包围的区域
捕获一个被包围区域的方法是将被包围区域中的所有‘O’变成‘X’
例如 
X X X X
X O O X
X X O X
O X X X
执行完你给出的函数以后，这个二维板应该变成：
X X X X
X X X X
X X X X
O X X X

参考答案

方法一(正向思维): 对于每一个点作为起点进行 dfs, 若此点值为 'X' 或者位于边界则跳过, 否则对此点的上下左右 4 个点进行同样的操作. 若 dfs 过程中能够到达区域边界, 则跳过此点; 若不能到达区域边界, 则以该点为起点重新进行上述条件的 dfs, 并标记遍历到的每一个点为 'X' 方法二(正难则反): 将区域中所有的 'O' 标记为 'Z'; 从区域中每一个边界的标记为 'Z' 的节点作为 dfs 的起点出发, 若遇到非 'Z' 节点则跳过, 并将遇到的 'Z' 节点标记为 'O'. 将区域中所有剩余的 'Z' 节点标记为 'X'.
纠错 收藏
查看讨论
上一题 下一题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号