プログラミングの課題。幅優先探索と動的計画法

今日は某プログラミング訓練サイトでアルゴリズムとそれをプログラムしてみた。なにかと苦戦して一日中格闘していた。難しかったけど解けた。アルゴリズムに対する理解と実践がようやく身についてきたような気がする。

 どういう問題だったかというと、「縦Rマス、横Cマスの迷路がある。これの最短手数を求めよ。条件は1<=R<=50, 1<=C<=50,通れるマスは . で通れないマスは#とする。」みたいな問題。問題は下図のような感じ。今回はコードの方は面倒なので載せません。違う機会があったら乗せると思う。

迷路で最短手数を求めるのに有効なのが、「幅優先探索」というのはポンコツの俺もずっと考えてたから理解できるようになった。しかし厄介なのが探索の範囲が広すぎると後半あたりでメモリが激増するところ。上の条件のC,Rの最大値が50までとれてそれに対応するにはメモリが増えすぎないようにしないといけない。最初は幅優先探索だけで解こうとしてそのメモリの問題に苦戦した。そこで「動的計画法」とセットでやれば高速化できてメモリがあまり必要なくなると思たった。

  上の迷路は文字なのでchar型の二次元配列を用意した。それとは別にint型の同じサイズの2次元配列を用意して、探索するごとにどれだけ進んだかをそのint型の配列に記憶していく。コード上ではこんな感じで宣言した。

const int N = 50;

char MAP[N + 1][N + 1];

int MAP2[N + 1][N + 1];

このMAP2配列に答えを逐一記録していく。

MAP2[y][x] = MAP2[一つ前のマスのy座標][一つ前のマスのx座標] + 1;

こういう感じで一つ前の座標の値を再利用してMAP2に記憶していけばかなり高速化できて幅優先探索のメモリも少なくて済んだ。これで解けましたとさ。