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

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

在下面的矩阵中给出:

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

找出在4个方向(上，下，左，右角)上是否有仅由R或B组成的组被相反的颜色包围。

例如:回答上述矩阵->第二行中B的有效集合，被R包围。

[[ 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处理，但无法解决问题。
有人可以指导我解决方案。

最佳答案

要找到被R细胞包围的B细胞组，可将矩阵视为一个图，其顶点均为B细胞，其边连接相邻的B细胞。使用BFS(或DFS)查找此图的connected components，但忽略边界上包含单元格的已连接组件。每个(无边界)连接的组件都包含一组由R单元包围的B单元。然后，要找到被B单元包围的R单元组，类似地计算其顶点为R单元的图的无边界连接分量。

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