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 に答える
1

このマップをグラフとしてモデル化し、各正方形が 4 つの隣接する正方形に接続されている場合、ブリッジ検出アルゴリズムを使用して必要な正方形を見つけることができます。

このモデルは、時々操作するいくつかのサブグラフを提供することに注意してください。そのため、#そこに を追加すると、いくつかのノードが残りのノードから確実に分離されるため、境界の周りに多数の誤検出が生じる可能性があります。これを回避するには、グラフの周りに2 レベルの四角形をパディング#して、境界ノードを残りのノードから分離できないようにすることができます。

@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 に答える