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

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

[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で埋める

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

[TarZ (28055)]

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

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

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

[okky (2487)]

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

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

--
fjの教祖様