算法-矩阵中另一种颜色包围的颜色

Question

我最近在一次采访中遇到了这个问题：

在矩阵下方给出：

[[ R R R R R R],
 [ R B B B R R],
 [ B R R R B B],
 [ R B R R R R]]

找出在以下四个方向上被相反颜色包围的only R's或only B's中的任何一组：上，下，左，右角。

ex：上面矩阵的答案->第二行中被R包围的B的有效集合。

[[ R R R R R R],
 [ R **B B B** R R],
 [ B R R R B B],
 [ R B R R R R]]

我尝试在所有方向上为特定颜色制作BFS，但无法解决。有人可以引导我找到解决方案。

Answer 1

要找到被R细胞包围的B细胞组，请将矩阵视为一个图，其顶点均为B细胞，其边连接相邻的B细胞。使用BFS（或DFS）查找此图的connected components，但忽略边界上包含单元格的已连接组件。每个（无边界）连接的组件都包含一组由R单元包围的B单元。在顶点为R单元的图上运行相同的算法，以找到被B单元围绕的R单元组。]

由于两个图的顶点和边数均为O(mn)，并且可以在与图大小成线性关系的时间中找到图的连接组件集，因此该算法的运行时间为O(mn)。] >