是否有一个算法来确定网格连续颜色的区域？

StackOverflow https://stackoverflow.com/questions/452480

  •  19-08-2019
  •  | 
  •  

题

给定一个基本格（像一块方格纸的），其中每个单元具有与n种颜色之一中被随机地填充在

，有没有尝试和真正的算法，有可以告诉我什么连续的区域（小区组这在侧面加入了相同颜色的）也有？比方说，n是合理的东西，像5。

我有一些想法，但他们都觉得太没效率了。

有帮助吗？

解决方案

在最佳可能的算法是O（数量的细胞），并且是不相关的颜色的数量。

这可以通过细胞迭代来实现，与您亲临每次一个，作为访问还没有被标记，做图的遍历查找该地区的所有连续的单元格，然后继续迭代。

编辑：

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

function visit(cell) {
    if cell.marked return
    cell.marked = true
    foreach neighbor in cell.neighbors {
        if cell.color == neighbor.color {
            visit(neighbor)
        }
    }
}

其他提示

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

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

您可以尝试在每平方米做一个颜色填充。作为洪水差，记录在一个阵列或东西的方格，和在未使用的颜色它们上色，说-1。

联盟找到将在这里工作为好。事实上，你可以制定一个关于图形的问题你的问题：顶点是网格单元和两个顶点是相邻的，如果他们的网格单元具有相同的颜色。你试图找到连接的部件。

你可以使用一个工会找到的数据结构的方法如下：首先用尽可能多的元素的合并 - 查找数据结构，你的细胞。然后通过细胞循环和union两个相邻小区，如果它们具有相同的颜色。最后，每个单元上运行find和存储的响应。用相同的find细胞在相同的连续的着色区域。

如果你想多一点细粒度控制，你可能会考虑使用 A * 算法，并使用启发式包括同样颜色的瓷砖。

您通过的区域中扫描线重复，去左右上下。对于每个小区你让作为小区之间的相同的存储对象共享的小区的列表。对于每一个细胞，你当前单元格添加到列表中（或者与它共享或创建）。然后，如果单元格右侧或下方是相同的颜色，你的分享与该小区该列表。如果该小区已经有一个列表，你把名单和替换在列出与新合并的列表中列出的每个单元格的引用到列表中的对象。

然后位于每个小区是到包含与该小区的每个连续单元的列表的参考。这恰如其分地结合每一个细胞之间此时，floodFill的工作。而不是重复它为每个小区。既然你有合并的数据替代数据列表只是通过一个列表进行迭代。这将是为O（n * C）其中n是细胞和c的数量的曲线图如何连续是一个量度。一个完全脱节电网将是n次。一个完全连续的1个色图表与是N ^ 2/2。

不隶属于 StackOverflow
scroll top