最短経路を探してみた

こんなものを見つけたので、試しにjavascriptでやってみた。
人材獲得作戦・4 試験問題ほか: 人生を書き換える者すらいた。


要はこんな迷路があったときに、スタート(S)からゴール(G)までの最短距離を見つけなさいとのこと。(等幅フォントじゃないと奇麗に表示されない!)

**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************

コードはこちらに置いときました!
http://jsdo.it/gibachan/drlz

考え方としては、ゴールから逆に辿ってスタートまでの経路を探しています。
ゴールの位置を0とし、その隣は1、そしてそのまた隣は2、3といった感じで、その場所までの最短ステップ数を再帰的に求めています。



ちょっとした息抜きでできるかと思ったけど、意外と時間がかかってしまった。
経路探索アルゴリズムは調べれば色々見つかるけど(ダイクストラ法とか)、こういったものがすぐに思いつかなくて、基礎がなってないなぁと反省。