有人知道在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

因此，最好的方法是找到“有限区域”，在这个区域中可以开始泛洪或其他填充算法来填充该有限区域。

- Kaltsoon

---

这个问题放在程序员上不是更好吗？ - zmo

我认为，算法取决于用于表示地图的数据结构。您能否更明确地说明您的实现（因为您已经标记了“图形”）？ - ibi0tux

我正在考虑将无向图作为一种数据结构，其中每个方块都是一个顶点，通过边与其他顶点相连。 - Kaltsoon

更精确地说明问题，并纠正示例中的错误（如果没有错误，则解释示例）。 - Bartosz Marcinkowski

看起来你正在寻找一个关键节点（articulation point）[链接]（http://en.wikipedia.org/wiki/Biconnected_component）。 - svick

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

- Vikas

Answer 2

如果我们将每个 # 视为点 x,y，我认为这个问题可以简化为凸包问题，然后凸包会给出所有缺失的 # 的 x,y 坐标。

http://en.wikipedia.org/wiki/Convex_hull

我会在闲暇时尝试编写它..

- sethi

---

这个算法需要修改，因为在这种情况下，节点必须相邻才能划分区域。 - ibi0tux

啥？凸包算法怎么会找到特定的4,5正方形呢？而且它不也会错误地找到1,2吗？ - svick

集合不一定是凸的，因此凸包并不能真正帮助很多。 - G. Bach

Answer 3

你可以通过处理每个“.”节点来攻击它。

定义: 如果不存在从节点到地图边界的路径，则“.”节点为封闭。

如果您同意上述定义，算法将是维护一个“.”节点的图形，其中相邻节点相连。

每次将一个节点更改为“＃”，请从该图中删除它，并检查每个剩余的“.”节点，以查看是否存在从它到地图边界上的节点的路径。

取决于您的地图大小，您可能需要尝试各种优化来限制每个回合执行的路径搜索数量。

- mbeckish

---

这是我在思考的一个问题。只是我正在制作一款游戏，每秒搜索每个空闲节点60次似乎有点沉重。 - Kaltsoon

大约300-350个左右。我认为这不算太多。 - Kaltsoon

我认为你要找的是泛洪填充。在这里查看：https://dev59.com/wHM_5IYBdhLWcg3wgzZl#1348995。 - mbeckish

如果您有一棵树，可以从边界到每个空闲点识别至少一条路径，那么搜索将变得更容易。当您声明一个点时，会从图中切断该点。通常情况下，这可能会分离一个或多个树。如果可以将它们重新连接到树的其他点上，请这样做（通常是对相邻点进行本地操作）。如果不能重新连接，则可以填充所有这些点。 - MSalters

@MSalters 这正是我在第一次看到这个问题时所想的。然而，为了正确地实现这一点，您需要找到一种方法来防止子树连接到其自己的分支。 - AJMansfield

@AJMansfield：这其实很简单，可以使用“边界距离”作为度量标准。 - MSalters

Answer 4

我会从选定方块的每个邻居开始，并尝试“逃脱”到网格的边界。同时，标记路径为“X”。如果你能逃脱：撤销所有“X”。如果你不能逃脱，则用“#”替换每个“X”。我在Java中做了一个示例，如下所示。

int W, H;   
char[][] input;
final int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

public void handle(int x, int y) {
    // try each neihgbor
    for (int[] d : directions) {
        if (canEscape(input, x, y)) {
            // if we can escape, the path found shouldn't be filled
            // so replace the Xes by '.';
            handleXes(input, false);                
        } else {
            // if we cannot escape, this is a closed shape, so
            // fill with '#'
            handleXes(input, true);
        }
        // note that this can be written more concisely as
        // handleXes(input, !canEscape(input, x, y));
    }
}    

public boolean canEscape(char[][] grid, int x, int y) {
    if (isEscape(grid, x, y))
        return true

    if (isValid(grid, x, y)) {
        // mark as visited
        grid[x][y] = 'X';
        // try each neighbor
        for (int[] d : directions) {
            if (canEscape(grid, x+d[0], y+d[1]))
                return true;
        }
    }

    return false;
}

public boolean isValid(char[][] grid, int x, int y) {
    return 0 <= x && x < W && 0 <= y && y < H && grid[x][y] == '.';
}

public boolean isEscape(char[][] grid, int x, int y) {
    return (0 == x || x == W-1 || 0 == y || y == H-1) && grid[x][y] == '.';
}   

public void handleXes(char[][] grid, boolean fill) {
    for (int x = 0; x < W; x++)
        for (int y = 0; y < H; y++)
            if (grid[x][y] == 'X')
                grid[x][y] = fill ? '#' : '.';
}

- Vincent van der Weele

Answer 5

如果您将此地图建模为一个图形，并且每个正方形都连接到其四个邻居，则可以使用桥梁查找算法来找到所需的正方形。

请注意，该模型有时会给您提供几个子图来处理，因此可能会在边界周围产生许多误报，因为在那里添加一个#肯定会将一些节点与其他节点分开。为了解决这个问题，您可以在图形周围填充两个级别的正方形，以便没有单个#可以将边界节点与其他节点分开。

@svick的评论启发了这种方法。

- zw324