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

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个方向上被相反的颜色包围：上、下、左, 右角.

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 单元。然后，求B细胞包围的R细胞群，同理计算以R细胞为顶点的图的非边界连通分量

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

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

Algorithm - Colour surrounded by another colour in a matrix

algorithm

breadth-first-search

matrix