有人知道在2d数组中找到"形状"的算法吗？

Question

我们来看看这张地图,其中'#'表示一个正方形和'.' 说明了一个自由方块:

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

现在,如果我在方块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