「某社の採用試験は迷路の最短経路探索プログラム」記事へのコメント

メモリいくら使ってもいいんですよね？

[TarZ (28055)]

1. 準備
   テキストからメモリに読み込む（unsigned int 2次元配列）。壁はオール0xff、空間は0x0、読み込みの際にSの位置を見つけておいて0x1、Gは0xfffffffe。
2. ループ
   1. 0x1の周囲の空間0x0を0x2で埋める。
      （メモリが潤沢ならここで0x2を埋めた座標を保存しておいて次のループで使う。メモリが少ないなら毎回2次元配列をフルスキャンして0x2を見つける）
   2. 0x2の周囲0x0を0x3で埋める。
   3. 数字を大きくしながら、1-2を繰り返す。数字が0xfffffffdになったら探索失敗。
   4. 埋める過程でG(0xfffffffe)が見つかれば探索終了。ゴール周囲の 0x4 -> 0x3 -> 0x2 を順に辿って 0x1まで 0xfffffffdで埋める。同じ数字が複数あるなら複数解があるので、そのうち1つをチョイスする（どれでもよい。どのルートも0x1に繋がっている）。
3. 壁、空間、0xfffffffdを$に置き換えて2次元配列をテキスト出力。

　最短経路が2^32-3ステップ未満ならこれでいけると思います。ゴールが見つかったときに打ち切らず、そのステップが終了するまで探索すれば、複数解がある場合も求められます。

　Cで30分くらいで書けるんじゃないかな。

Re:メモリいくら使ってもいいんですよね？

[TarZ (28055)]

　おおっと。他のコメント読んでいませんでしたが、okkyさんとほぼ同じでしたか。ちなみにこのやり方なら、迷路が長方形であろうとなかろうと（壁で囲まれているなら）使えます。

　最短経路より短い経路は全て調べつくし、それより長い経路は調べないので、直感ですが探索量は最小だと予想します。アルゴリズムも単純なので、バグが少なく短時間で組める点もメリットです。
　リンク先の「Lv4の2名」も似たような方法で解いたと思いますが、もしこれ以外の方法で解いたのならどんな方法だか興味があります。

Re:メモリいくら使ってもいいんですよね？

[okky (2487)]

迷路が長方形であろうとなかろうと（壁で囲まれているなら）使えます。

それは与えられたダンジョンの周囲に、もう一周、番兵(この場合は壁ですね)を別途張ってあげれば解決すると思います。潤沢にメモリを使って良くて、なおかつアドレス空間も腐るほどあると仮定していいなら、これが簡単。

--
fjの教祖様