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

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]]

找出是否有任何一组只有 R 或只有 B 被 4 个方向上的相反颜色包围:上、下、左、右角。

例如:上述矩阵的答案 -> 在第二行中被 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 单元格。然后，为了找到被 B 细胞包围的 R 细胞组，类似地计算顶点是 R 细胞的图的非边界连通分量。

由于两个图的顶点数和边数都是O(mn)并且可以在与图的大小成线性关系的时间内找到图的连通分量集，该算法的运行时间为O(mn) .