我们如何找到具有两个不同“ID”的图的最大连续区域？

Question

我最近了解了Flood-Fill Algorithm，这是一种可以获取图形并O(N)及时为每个节点分配组件编号的算法。

例如，可以使用 Flood-Fill 算法有效解决的一个常见问题是找到一块N*N板上最大的区域，其中该区域中的每个节点都与另一个具有相同 ID 的节点相邻，或者直接向上、向下、到向左，或向右。

在这个棋盘中，最大的区域都是 3，分别由全 1 和全 9 组成。

然而，我最近开始怀疑我们是否可以扩展这个问题；具体来说，如果我们能在图中找到最大的区域，使得该区域中的每个节点都与具有两个可能 ID 的另一个节点相邻。在上图中，最大的此类区域由 1 和 9 组成，大小为 7。

这是我试图解决这个问题的思考过程：

想法 1：O(N^4) 算法

我们可以O(N^4)使用基本的洪水填充算法及时解决这个问题。我们通过测试所有O(N^2)水平或垂直相邻的方块对来做到这一点。对于每一对方块，如果它们有不同的 ID，那么我们从两个方块中的一个运行填充。

然后，通过修改洪水填充算法，使其传播到具有两个可能 ID 之一的正方形，我们可以及时测试每一对O(N^2)--> O(N^2) pairs * O(N^2) flood fill per pair = O(N^4) algorithm。

然后，我有了一个洞见：An Possably O(N^2) Algorithm

首先，我们通过电路板运行常规的洪水填充并将电路板分成一个“组件图”（其中原始图中的每个组件都减少为单个节点）。

现在，我们通过组件图的边缘而不是节点进行洪水填充。我们用一对整数标记每条边，表示它连接的两个组件内的两个 ID，然后通过边填充，就好像它们本身是节点一样。

我相信，如果正确实施，将产生一种O(N^2)算法，因为N*N板中边数的上限是4*N*N.

现在，我的问题是，我的思维过程在逻辑上是否合理？如果没有，有人可以建议另一种算法来解决这个问题吗？

Answer 1

你的算法有效...

据我所知，对诱导图的洪水填充确实给出了所有可能的组件，之后很容易找到最大的组件。

...但我不确定运行时间

您正确地说O(N^2)原始图中存在边，因此O(N^2)归纳图中存在节点。然而，这些节点不再保证位于良好的网格中，这可能会留下比O(N^2)诱导边缘更多的网格。

例如，考虑示例中的大“1-block”。该块有 6 条边，这将给出一个具有 6 个顶点的完整图，因为所有这些边转向的顶点都是相连的。这可能会给你一个包含多个O(N^2)边的归纳图，从而无法在 O(N^2) 时间内找到组件。

因此，我相信该算法不会在 中运行O(N^2)，但我不确定实际的运行时间，因为这将取决于算法此时具体执行的操作。题主只注意到洪水补，但我想它没有想象到这种情况。

考虑以下9x9网格：

232323232
311111113
212313212
313212313
212313212
313212313
212313212
313212313
212313212

这个想法很简单：它是一个单一的大型组件，旨在与尽可能多的小组件接壤。这里的导出图将是一个具有O(N^2)顶点和O(N^4)边的几乎完整的图。或者，如果我们仅将 (1,2) 边与其他 (1,2) 边连接，并且 (1,3) 边和其他 (1,3) 边类似，我们将得到一个连接稍微少的图，但它仍然由每个O(N^4)边的两个分量组成，尽管常数较低。

因此，创建这个图至少需要O(N^4)时间，遍历它也需要时间。我认为这是该算法所花费的时间，但我无法证明没有可能的优化可以对此进行改进。