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

问题描述

让我们以这张地图为例，其中#"表示所取的正方形和.".说明一个自由正方形:

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

那么，找到有限方块"的最佳方法是什么，我可以在那里开始填充或其他填充有限区域的填充算法?

解决方案

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

如果我这样定义图表:

G = (V, E)V = {r1, r2, r3, r4, r5, r6, c1, c2, c3, c4, c5, c6}E = {(u, v) |u、v 是 V && 的元素单元格(u，v)未被采用}

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

对于 V 中的每个 u:颜色[u] = 白色对于 V 中的每个 u:如果颜色[u] == 白色:contains_boundary_edge = FalseDFS-visit(u, contains_boundary_edge)如果不是 contains_boundary_edge:泛洪( u )DFS-visit(u, contains_boundary_edge):颜色[u] = 灰色对于相邻( u )中的每个 v:如果颜色[v] == 白色:if edge(u, v) is a boundary edge://如果 u, v 之一是开始或结束行/列，可以很容易地识别.contains_boundary_edge = TrueDFS-visit( v, contains_boundary_edge )颜色[u] = 黑色

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

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.

If I define the graph like this:

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}

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屋！