1

単純なマトリックス（2Dゲームで地形図を表すマトリックス。たとえば、山の場合は「m」、谷の場合は「v」、川の場合は「r」などのASCII文字が含まれます）があり、マップ上には川が1つまたはまったくない可能性があります。川は、マトリックスから任意の位置に流れることができます（そして、常に2つの異なる部分で別々のマップ=>マップ上の川のソースは不可能であり、常に一方の端から入り、もう一方の端に存在します）。川が存在する場合、2つのクラスターでマトリックス/地形図を分離するにはどうすればよいですか？

地形の例

v v v v v v v v r v v v v v 
v v v v v m m m r m m m m m
v v v v v m m r r m m m m m
m m v m m m m r r m m m v v 
v v v v v v r r v v v v v v

ここでは、川ではない座標の左クラスターと右クラスターを取得する必要があります。

4

2 に答える 2

4

塗りつぶしアルゴリズムを調べてみてください。 http://en.wikipedia.org/wiki/Flood_fill

基本的に、川にないポイントを選択する場合は、開始ポイントに接続されたポイントのセットを提供するフラッドフィルアルゴリズムを開始します。このようにして、1つのパーツが作成され、これからは1つのパーツを見つけるのが非常に簡単になります。

于 2013-03-20T14:39:09.993 に答える
2

あなたの地図はグラフを誘発します：

  • マップセルごとに1つの頂点があります
  • 2つの頂点が隣接していて、いずれも「r」でない場合は、2つの頂点が接続されています。

グラフが作成されたら、幅優先探索（BFS）や深さ優先探索（DFS）などのグラフ走査アルゴリズムを実行して、グラフの連結成分を見つけることができます。

マップが大きい場合、DFSによってスタックオーバーフローが発生する可能性があるため、BFSを使用することをお勧めします（再帰的な実装が使用されている場合）。

「r」以外のノードでのみBFSを実行することをお勧めします。これにより、最終的に2つのコンポーネントが接続されます。

于 2013-03-20T14:55:42.487 に答える