迷路プログラム

迷路プログラムの応用問題なのですが、上手くいかずに困っています。

問題
2次配列を用いて、縦横X,Yマスの迷路を作ります。
マスの数はX,Y共に最大100までの値であれば、任意の数が振れます。
迷路の一番左下がスタートS、一番右上がゴールGになります。

マスへは上下左右にしか移動出来ません。
迷路の中には任意で入力したXマスがあり、Xが入っているマスには移動出来ません。
S,G,Xが入っていないマスには、1～9までの数字を任意に入力します。
それぞれの数字は、そのマスに移動するためにかかるコストを表しています。
スタートからゴールまで、コストがもっとも小さくすむルートのコストを出力するプログラムを作りたいです。
また、Xマスでゴールが不可能な場合は-1を返します。

単純にゴールを目指すのと違い、コストがあると遠回りをしなければならない可能性があるので、そのアルゴリズムが思いつきませんでした。

例 11*7マスの迷路の場合

マスの数：11 7

迷路の値の入力：
7 9 3 3 6 3 X X 7 9 G
1 1 3 2 6 6 8 4 8 4 5
7 2 9 1 3 4 8 4 9 8 9
9 7 4 2 5 X 8 6 9 9 4
4 7 3 8 X 8 X 5 7 X 7
1 7 1 8 5 6 5 9 5 6 2
S 5 5 2 9 4 2 2 9 5 1

出力：
最小コストは59


迷路からゴールに進むだけのプログラムは作れたのですが、応用問題としてコストが入ると急に難しくなりました。
コストが絡むとどういうアルゴリズムで動けばいいのか分かりません。アドバイスをお願いします。

No.2 ベストアンサー 回答者： Tacosan 回答日時： 2008/06/14 01:19

「迷路」と思うと難しいかもしれないけど, よく考えるとただの「最短経路探索」です. これにもいろいろな方法があるけど, コストが全

て正なら Dijkstra のアルゴリズムが普通だと思います.

この回答へのお礼

ダイクストラ法で動かす事が出来ました。
ありがとうございました。

お礼日時：2008/06/14 16:44

No.1 回答者： asuncion 回答日時： 2008/06/13 23:17

バックトラック法による全ルート探索でしょうか。

最小コストのルートを求めなければなりませんので、
どういうデータ構造を使うかも肝心な点だと思います。

この回答へのお礼

ダイクストラ法で試してみたところ、無事に動きました。
バックトラック法というのもあるのですね、勉強になりました。

お礼日時：2008/06/14 16:44