迷路プログラム
迷路プログラムの応用問題なのですが、上手くいかずに困っています。
問題
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
迷路からゴールに進むだけのプログラムは作れたのですが、応用問題としてコストが入ると急に難しくなりました。
コストが絡むとどういうアルゴリズムで動けばいいのか分かりません。アドバイスをお願いします。
お礼
迷路だけではないので、おもしろそうですね。 ありがとうございました。