14

让我们看这张地图，其中“#”表示一个已拍摄的正方形和“.”。说明了一个自由正方形：

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

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

4

5 回答 5

6

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

如果我这样定义图表：

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
于 2013-06-17T14:33:51.443 回答
3

我认为这个问题可以简化为一个凸包问题，如果我们将每个 # 视为点 x,y 然后凸包给我们所有不存在的 # 的 x,y

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

我会尝试在闲暇时对其进行编码..

于 2013-06-17T14:21:28.617 回答
2

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

定义：一个'.' 如果不存在从节点到地图边界的路径，则将节点括起来。

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

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

根据地图的大小，您需要尝试各种优化来限制每回合执行的路径搜索次数。

于 2013-06-17T14:26:58.253 回答
1

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

请注意，此模型有时会为您提供几个可以使用的子图，因此它可能会在边界周围产生许多误报，因为添加 a#肯定会将一些节点与其他节点分开。为了解决这个问题，您可以在图形周围填充两层正方形，这样没有一个#可以将边界节点与其余节点分开。

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

于 2013-06-17T14:31:07.643 回答
1

我会从所选正方形的每个邻居开始，并尝试“逃逸”到网格的边界。同时，用“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 ? '#' : '.';
}
于 2013-06-17T14:31:32.260 回答