是否有算法来确定网格中连续的彩色区域？

Question

给定一个基本网格(如一张方格纸),其中每个单元格随机填入n种颜色中的一种,是否有一个经过验证的真实算法可以告诉我哪些连续区域(相同的单元格组)在侧面连接的颜色)有？让我们说n是合理的,比如5.

我有一些想法,但他们都感到非常低效.

Answer 1

最好的算法是O(单元数),与颜色数无关.

这可以通过遍历单元格来实现,并且每次访问未标记为已访问的单元格时,执行图形遍历以查找该区域中的所有连续单元格,然后继续迭代.

编辑:

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

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

Answer 2

除了递归的递归答案,如果递归太慢,你可以使用堆栈:

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