コグノスケ

タイムトライアルは苦手です

研究室のWikiでIKeJIから教えてもらったこの問題（参照: 人生を書き換える者すらいた。: 人材獲得作戦4試験問題ほか）にトライしてみました。

手元にあった環境とC言語でトライしたところ、19:38開始、21:18終了、所要時間1時間40分でした。回答はこんな感じです。

$ ./a.out < meiro.dat
found the goal depth=60
**************************
*S* * $$$                *
*$* *$$*$ *************  *
*$* $$* $  ************  *
*$$$$*  $$$$$$$          *
**************$***********
* $$$$$$$$$$$$$          *
**$***********************
* $$$  * $$$$$$$$$$$$$G  *
*  *$$$$$$*********** *  *
*    *        ******* *  *
*       *                *
**************************

出力結果は上記サイトの基準でいうLv4達成（※）です。

苦戦したところはダイクストラ法の実装です。ダイクストラ法なんかは基本中の基本のアルゴリズムですが、結構忘れていて手間取りました。

一応 ソースコードも載せておきます。頭に修正BSDライセンスの条文を追加した以外、全てそのままです。

リファクタリングも何もしていませんので、変なコメント、グローバル変数乱発、意味不明な変数名、デバッグ用コード、ゴールできないときハングするバグ（※2）も恥ずかしながらそのままです。

迷路一歩進む度に、迷路の全域をチェックするなどモサい実装ですが、これが現状発揮できる自身の実力の一つであることには違いないです。よって今後も精進あるのみです。

（※）ダイクストラ法は常に最適解、この問題の場合でいえばゴールまでの最短距離を得られるためです。証明は習った気がしますが忘れました…。

（※2）ゴールへの経路がない場合「not found the goal」と出力しますが、returnし忘れているため、その後のパスのバックトレース部分に突入してしまい、無限ループに陥ってハングします。
日記を書いているときに気がつきました。ひどすぎですね、これ。