任何人都知道用于寻找“形状”的算法。在二维数组中？ [英] Anyone knows an algorithm for finding "shapes" in 2d arrays?

问题描述

让我们来看看这张地图，其中＃表示一个已取正方形，而。表示一个自由正方形：

Let's take this map, where '#' illustrates a taken square and '.' illustrates a free square:

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

现在，如果我在正方形4,5区域中放置＃会像这样填充：

Now, if I put a '#' in the square 4,5 the area would be "filled" like this:

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

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

So, what is the best way to find "a limited square", where I can start flood fill or other filling algorithm that fills the limited area?

推荐答案

如果您可以将问题转换为图形，那么您正在寻找的是识别连接的组件。如果连接的零部件不包含边界线，那么您已经找到了需要填充的区域。

If you can convert your problem to a graph, what you are looking for is to identify connected components. And if a connected component does not contain an edge that is the boundary edge, then you have found the region that needs to be filled.

如果我这样定义图形：

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 查找所有断开连接的树。算法：

Now run DFS to find all disconnected trees. Algorithm:

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

这篇关于任何人都知道用于寻找“形状”的算法。在二维数组中？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！