10

给定一个基本网格（如一张方格纸），其中每个单元格都随机填充了 n 种颜色中的一种，是否有一种经过验证的真实算法可以告诉我哪些连续区域（相同的单元格组侧面连接的颜色）有吗？假设 n 是合理的，比如 5。

我有一些想法，但他们都觉得非常低效。

4

8 回答 8

10

最好的算法是 O（细胞数），与颜色的数量无关。

这可以通过遍历单元格来实现，每次访问尚未标记为已访问的单元格时，进行图遍历以找到该区域中的所有连续单元格，然后继续迭代。

编辑：

这是一个简单的深度优先搜索伪代码示例，这是一个易于实现的图遍历：

function visit(cell) {
    if cell.marked return
    cell.marked = true
    foreach neighbor in cell.neighbors {
        if cell.color == neighbor.color {
            visit(neighbor)
        }
    }
}
于 2009-01-17T00:02:47.280 回答
7

除了递归的递归答案，如果递归太慢，您可以使用堆栈：

function visit(cell) {
    stack = new stack
    stack.push cell

    while not stack.empty {
        cell = stack.pop
        if cell.marked continue
        cell.marked = true
        foreach neighbor in cell.neighbors {
            if cell.color == neighbor.color {
                stack.push neighbor
            }
        }
    }
}
于 2009-01-17T00:35:47.400 回答
3

您可以尝试在每个方格上进行洪水填充。随着洪水的蔓延，将网格正方形记录在数组或其他东西中，并将它们涂上未使用的颜色，例如-1。

于 2009-01-17T00:01:33.257 回答
3

关于洪水填充的维基百科文章可能对您有用：http ://en.wikipedia.org/wiki/Flood_fill

于 2009-01-17T00:07:58.127 回答
2

Union-find也可以在这里工作。实际上，您可以将您的问题表述为关于图的问题：顶点是网格单元，如果两个顶点的网格单元具有相同的颜色，则它们是相邻的。您正在尝试查找连接的组件。

使用 union-find 数据结构的方式如下：首先创建一个 union-find 数据结构，其中包含与单元格一样多的元素。然后遍历单元格，union如果它们具有相同的颜色，则遍历两个相邻的单元格。最后，find在每个单元上运行并存储响应。具有相同颜色的单元格find位于相同的连续彩色区域中。

于 2009-01-17T00:57:32.693 回答
0

如果您想要更细粒度的控制，您可能会考虑使用A*算法并使用启发式方法来包含类似颜色的图块。

于 2009-01-18T20:13:06.363 回答
0

您遍历扫描线中的区域，从左到右从上到下。对于每个单元格，您创建一个单元格列表，这些单元格在单元格之间共享为相同的内存对象。对于每个单元格，您将当前单元格添加到列表中（与其共享或创建）。然后，如果右侧或下方的单元格颜色相同，您将与该单元格共享该列表。如果该单元格已经有一个列表，则合并列表并将列表中列出的每个单元格中对列表对象的引用替换为新的合并列表。

然后位于每个单元格中的是对包含该单元格的每个连续单元格的列表的引用。这恰当地结合了每个单元之间的填充工作。而不是为每个单元格重复它。由于您有列表用合并的数据替换数据，因此只是迭代列表。它将是 O(n*c)，其中 n 是单元格的数量，c 是图形连续性的度量。一个完全脱节的网格将是 n 次。一个完全连续的 1 颜色图，为 n^2/2。

于 2018-11-18T17:12:16.163 回答
0

我在视频中听到了这个问题，也在这里找到了它，我想出了我在搜索中看到的最佳方法。以下是算法的基本步骤：

  • 从左上角到右下角循环遍历数组（假设颜色网格表示为二维数组）。
  • 当你浏览第一行时，只需检查左边的颜色，看看它是否是相同的颜色。当您遍历所有后续行时，检查上方的单元格和左侧的单元格 - 这比每次检查顶部、底部、左侧和右侧更有效。不要忘记检查左侧单元格是否超出范围。
  • 创建一个类型的字典，<int,Dictionary<int,Hashset<cell>>>用于在这些颜色中存储颜色和组。Hashset 包含单元格位置（具有 2 个属性的单元格对象：int 行、int 列）。
  • 如果单元格没有在顶部或左侧连接到相同颜色的单元格，则创建一个新的字典条目，在该条目中创建一个新的颜色组，并将当前单元格添加到该组（哈希集）。否则它连接到另一个相同颜色的单元格；将当前单元格添加到包含它所连接的单元格的颜色组。
  • 如果在某个时候您遇到一个在顶部和左侧具有相同颜色的单元格，如果它们都属于相同的颜色组，那么这很容易，只需将当前单元格添加到该颜色组即可。否则检查左上角的小猫角单元格。如果它与当前单元格的颜色不同，并且顶部的单元格和左侧的单元格属于不同的颜色组 --> 将 2 个颜色组合并在一起；将当前单元格添加到组中。
  • 最后，遍历所有 Hashset 以查看哪个具有最高计数 - 这将是返回值。

这是我制作的带有视觉和完整解释的视频的链接： https ://d.tube/#!/v/israelgeeksout77/wm2ax1vpu3y

PS 我在 GeeksForGeeks 上找到了这篇文章https://www.geeksforgeeks.org/largest-connected-component-on-a-grid/

他们方便地以多种语言发布了这个问题的源代码！但是我尝试了他们的代码和我的代码，我的运行时间大约是 1/3。

于 2021-10-05T06:39:49.947 回答