C/C++の宿題片付けます 126代目

C/C++の宿題片付けます 126代目 at TECH

180:デフォルトの名無しさん
09/05/23 20:48:53
>>173
最短経路が必要な場合は、２DRPGの最短移動アルゴリズムを使えばいいよ。

12x12の配列Aをワークとして用意する。型はintでいいや。
Aはすべて-1で初期化しておく。
まずスタート地点の決定。これは総当たりだから省略。
現在の探索深度を示すワーク int depth を用意して0に初期化する。
さて探索だけど、

1.スタート地点を現在値nowPositionに設定して、それに対応するAに０を代入する。
2.Aを全探索して、値がdepthになっているものがあれば、
　その上下左右(斜めも移動できるなら斜めも）に移動可能かどうかを
　調べる。移動可能で、かつその位置に対応するAが-1なら、その位置に
　depth+1を書き込む。
　移動可能な位置がゴールなら終了。４へ。
3.A全体を操作し終わるまで調べて、ひとつもdepthがなければ終了。ゴールには到達できない。
　１つでもdepthがあれば、++depthして、２を繰り返す。

4.ここからが最短経路探索。
　まずゴールには到達しているから、ゴールのdepthは分かってる。
　そこから上下左右のAの値が depth-1 になっている位置が最短経路。
　複数ある場合の処理は好きなようにすればいいが、今回は単純に最初に
　みつかった場所へ移動すればいいだろう。
5.これを繰り返してスタートに到達するまで続ける。なおスタートには必ず到達できる。

次ページ

続きを表示

1を表示