0

マップ上で森のすべてのクラスターを見つける方法は？私は（Type is enum {RIVER、FOREST、GRASS、HILL}のような単純なクラスセルを持っています

class Cell{
   public:
     Type type;
     int x;
     int y
};

とマップのようにvector<Cell> grid。リストに同じクラスター内のFORESTセルが含まれる場所を作成するアルゴリズムを誰かが提案できますかlist<list<Cell>> clusters（クラスターは接続されたセルのセットです-接続は8方向にできます：up、down、left、right、up_right、up_left、down_left、down_right）？マップ上で森のすべてのクラスターを見つけて、すべてのクラスターをに配置する必要がありますlist<Cell>。

4

2 に答える 2

1

アルゴリズムはかなり単純で、実際にはクラスターが何であるかの正確な定義にも依存しません。とが同じクラスターにある場合cluster(f0, f1)に生成される述語があるとします。あなたがする必要があるのは、森の中を走って見つけることだけです。セルがフォレストの場合は、既知のフォレストごとにチェックします。が得られる場合は、 のクラスターに追加します。他のクラスター内の他の既知のフォレストを引き続きチェックします。別のクラスター内に別のセルがあり、収量もある場合は、2 つのクラスターをマージ ( ) します。truef0f1gridfcluster(f, other)cluster(f, other)truefotherccluster(f, c)truestd::list<Cell>::spice()

于 2012-10-01T21:28:16.967 に答える
1

私はこれをコメントとして入れましたが、答えても構いません：

union-find アルゴリズムを調べます。パス圧縮を使用すると、後で構造をたどって各ルートのリストを作成し、セルを適切なリストに追加することができます。

リンク: http://en.wikipedia.org/wiki/Disjoint-set_data_structure

すべてのセルについて、上と左のセルで和集合を実行します。対角線を結合する場合は、左上と右上の対角線も含めます)。

クラスタ内のすべてのノードが単一のルートを指すように、union-find のパス圧縮バージョンを使用します。あとは、(すべてのユニオンを実行した後) 構造をウォークスルーし、ノードを追加するだけです。疑似 (らしい) コード:

foreach node
    Find(node)               // this ensures path compression

    if not clusters.hasList(node.root)
        clusters.createList(node.root)
    end

    list <- clusters.getList(node.root)
    list.append(node)
end

上記は、ノードがルートである場合、 をnode.root指すと仮定していますnode。

于 2012-10-01T21:36:18.300 に答える