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

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(查找此图的连接组件，但忽略边界上包含单元格的连接组件。每个(非边界(连接的组件都包含一组由 R 单元格包围的 B 单元格。然后，要找到被 B 单元格包围的 R 单元格组，同样计算图形的非边界连接分量，其顶点是 R 单元格。

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