Red and Black 解説

アルゴリズムの概略

いわゆる領域の塗りつぶし問題で,再帰関数を書けば簡単に解けます。 この問題は再帰関数を書き慣れていない人が最初に手をつけるのにちょうどよい問題だと思います。

開始地点(この問題では'@')から再帰関数を呼び出します。 再帰関数では,カウントを1つ足して,上下左右のマスに対して再帰関数を呼び出します。 呼び出すマスが壁(この問題では赤タイル'#')だったり盤上の外だったらカウントは行いません。 一度呼び出されたマスには,すでに呼び出されたことを示す印を書いておく必要があります。

この操作によって,開始地点から「上下左右の移動」で到達できるマスを全て調べることができます。 ループを使っても同等のプログラムは書けますが,この場合は再帰関数を使った方が直感的で考えやすいと思います。

アルゴリズムの計算量

一度呼び出されたマスは再度計算されないので,計算量はマス目の数で O(w×h) になります。 この問題では 0 < W, H <= 20 なので 400 程度で,全く問題ありません。

アルゴリズムの実装

ACM/ICPCで再帰関数を使う場合,いくつかの注意点(テクニック)があります。 まず,フィールドの大きさ(WやH)のような変数はできるだけグローバル変数として宣言しておきます。 そうすると main 関数で初期化して再帰関数を呼び出すときにわざわざ引数を増やす必要がありません。 数千行以上のプログラムを書く場合はグローバル変数を使いすぎると保守性が下がりますが, 保守を考える必要のない100行程度のプログラムでは開発効率が上がって得なのですね。

それから,再帰関数で枝刈りする際には,呼び出された後の先頭で枝刈りするよりも,呼び出す前に枝刈りした方がプログラムは速くなります。 この問題の場合,上下左右で再帰呼び出しを行いますが,「それぞれのマス目が壁である,もしくはすでにチェック済みである」場合はそのマス目に対してそれ以上再帰処理を継続しません(これを枝刈りと呼びます)。 その場合,再帰関数の先頭でチェックして return するよりも,呼び出す前にチェックしてそもそも呼び出さないようにした方がそこそこプログラムの速度が向上します。 どれくらい速度に違いがあるかというと,経験的にはだいたい10倍くらいの差だと思います。 これは関数呼び出しを行う際,現在の状況をスタックに積んだり戻したりする処理(プログラムカウンタやレジスタの退避)がけっこうなオーバーヘッドになるからです。 この問題では下手をしても大丈夫ですが,一般的に枝刈り探索を行う場合はけっこう違ってくるので気をつけてください。

あと,2次元配列は f[x][y] ではなく f[y][x] のようにすると入力処理が簡潔になりやすいです。

ループ実装による別解

再帰関数による実装はループによる実装に,ループによる実装は再帰関数による実装に,等価的に書き換えが可能です。 1979-deq_loop.cppでは(完全に等価ではありませんが)whileループによる実装を行ったので参考にしてください。 再帰とループのどちらで実装するかの判断は,どちらの方がバグを生み出さずに簡潔に実装できるかに依ります。

$Id: index.shtml 1335 2007-03-01 09:06:39Z SYSTEM $