algorithm - グリッド内の連続した色の領域を決定するアルゴリズムはありますか?

Question

各セルが n 色のいずれかでランダムに塗りつぶされている基本的なグリッド (方眼紙のようなもの) が与えられた場合、隣接する領域 (同じセルのグループ側で結合されている色) はありますか? n が 5 のような妥当なものだとしましょう。

いくつかのアイデアはありますが、どれも恐ろしく非効率的です。

Answer 1

最適なアルゴリズムは O(セルの数) であり、色の数には関係ありません。

これは、セルを反復することで実現できます。訪問済みとしてマークされていないセルを訪問するたびに、グラフ走査を実行して、その領域内のすべての連続するセルを見つけてから、反復を続けます。

編集：

以下は、深さ優先検索の単純な疑似コードの例です。これは、グラフ トラバーサルを簡単に実装できます。

function visit(cell) {
    if cell.marked return
    cell.marked = true
    foreach neighbor in cell.neighbors {
        if cell.color == neighbor.color {
            visit(neighbor)
        }
    }
}

Answer 2

再帰の再帰的な答えに加えて、再帰が遅すぎる場合はスタックを使用できます。

function visit(cell) {
    stack = new stack
    stack.push cell

    while not stack.empty {
        cell = stack.pop
        if cell.marked continue
        cell.marked = true
        foreach neighbor in cell.neighbors {
            if cell.color == neighbor.color {
                stack.push neighbor
            }
        }
    }
}

Answer 3

各正方形にフラッド フィルを実行してみてください。洪水が広がるにつれて、グリッドの正方形を配列または何かに記録し、未使用の色、たとえば -1 で色付けします。

Answer 4

フラッド フィルに関するウィキペディアの記事が役に立つかもしれません: http://en.wikipedia.org/wiki/Flood_fill

Answer 5

Union-findはここでも機能します。実際、質問をグラフに関する問題として定式化できます。頂点はグリッド セルであり、グリッド セルが同じ色の場合、2 つの頂点は隣接しています。接続されたコンポーネントを見つけようとしています。

共用体検索データ構造を使用する方法は次のとおりです。最初に、セルと同じ数の要素を持つ共用体検索データ構造を作成します。次に、セルとunion、同じ色の場合は隣接する 2 つのセルを反復処理します。最後に、find各セルで実行し、応答を保存します。同じセルはfind、同じ連続した色の領域にあります。

Answer 6

もう少し細かい制御が必要な場合は、A*アルゴリズムの使用を検討し、ヒューリスティックを使用して同様の色のタイルを含めることができます。