Curling 2.0 解説

アルゴリズムの概略と計算量

探索問題です。 探索の深さが10を超えれば失敗とみなして -1 を出力せよとあるので, 全探索をしても(上下左右で4通りなので)最大 410 = 1,048,576 = 1M なので解けてしまいます。

ですから,後は問題で与えられた通りに注意深く実装するだけです。 注意点としては,「当たった壁が消える」ことと,「ゴールの上にはそこで止まらなくてもOK」ということくらいでしょう。

アルゴリズムの実装

探索には深さ優先探索 (DFS: Depth First Search) と幅優先 (BFS: Breadth First Search) があります。 DFSでは単純に再帰関数を呼び出していけばいいので簡単なのですが,幅優先探索はキューなどに次に探索する状態を保持しておかないといけないので, 深さ優先探索に比べてコーディングが難しくなります。

もし(必ず)解があるのであれば,その解のある深さで探索を打ち切れるのでBFSの方が早くなります。 しかし,解がなければ結局全探索しなければならないので,DFSとBFSの計算量は等しくなります。 この問題では解がない場合もあるので,最悪の計算量はDFSとBFSは等しくなってしまい,BFSの恩恵は受けられません (ICPCでは現実世界とは違って平均的な計算量よりも最悪の計算量が大切です)。

ですので,この問題ではコーディングが簡単なDFSを採用するのがバグも少なくなってICPC的に良いでしょう。 特に(解答ソースコードにあるように)フィールドの状態をグローバル変数にしてそれを書き換えながら再帰関数で呼び出していくと簡単です。

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