人材獲得作戦・４ 試験問題ほか
さて試験問題です。内容は、壁とスペースで構成された迷路が与えられたとき、スタート地点からゴール地点に至る最短経路を求めよ、というものです。
とりあえず Perl で書いてみました。正確な時間は測っていないけれど(途中で熱中して時間のことを完全に忘れていた)、多分１時間くらいかな？ 最後の20分は見栄えの調整だったような気がしますが(汗) せっかく Perl を使ったのに Perl っぽくないというか C 言語っぽい香りがします。何故だろう。
処理ごとに関数で括っています。迷路を初期化→各マスまでの最短到達距離を求める→ゴールからスタートまでマーキング→画面に出す、という感じ。アルゴリズムの肝は最短到達距離を求める部分で、A*(エースター)だとかαβ枝狩りだとか色々テクニックはあるらしいんですが、多分、使っていません。普通にゼロからロジックを考えて実装しました。なので、アルゴリズムを知っている方が有利だとか、というのは多分無い。理論的に考える能力があって、時間をかければ誰でも解ける問題ですね。というわけで、ぐだぐだ言ってる奴はコード書けよハゲ。なかなか面白かった。
えーっと、話を戻して最短到達距離の求め方は、1) 隣のマスに移動すると歩数+1、2) 既に到達したマスでも、到達距離が今の方が短ければ、その値でアップデート、というルールだけで、これを盤面全体でぐるーっと回してやれば、盤面上の各点に移動するための最短距離が得られます。ゴールに関係なく、盤面全体で処理しているので効率悪いけど。
グローバル変数と変数の使いまわしはexcuse。
