algorithm - 有人知道在二维数组中查找 "shapes"的算法吗？

Question

让我们看看这张 map ，其中“#”代表一个被占用的正方形和“.”说明了一个自由广场:

1 . # # # . .2 . # . . # .3 # . . . . #4 . # # # . .5 . . . . . .6 . . . . . .- 1 2 3 4 5 6

现在，如果我在方 block 4,5 中放置一个“#”，该区域将像这样“填充”:

1 . # # # . .2 . # # # # .3 # # # # # #4 . # # # # .5 . . . . . .6 . . . . . .- 1 2 3 4 5 6

那么，找到“有限正方形”的最佳方法是什么，我可以在其中开始洪水填充或其他填充有限区域的填充算法？

Answer 1

如果您可以将您的问题转换为图表，那么您正在寻找的是识别连接的组件。如果连通分量不包含作为边界边的边，则您已找到需要填充的区域。

如果我这样定义图表:

G = (V, E)
V = {r1, r2, r3, r4, r5, r6, c1, c2, c3, c4, c5, c6}
E = {(u, v) | u, v are elements of V && the cell(u, v) is not taken}

现在运行 DFS 来查找所有断开连接的树。算法:

for each u in V:
    color[u] = white

for each u in V:
    if color[u] == white:
        contains_boundary_edge = False
        DFS-visit( u, contains_boundary_edge )

        if not contains_boundary_edge:
            Flood-fill( u )

DFS-visit( u, contains_boundary_edge ):
    color[u] = gray
    for each v in adjacent( u ):
        if color[v] == white:
            if edge(u, v) is a boundary edge: // Can be easily identified if one of u, v is start or end row/col.
                contains_boundary_edge = True

            DFS-visit( v, contains_boundary_edge )

    color[u] = black