Mysterious Gems 解説

アルゴリズムの概略

field[y][x] = 1 として宝石を配置し,移動した地点では field[y][x] = 0 にしていく。 お掃除ロボット。

アルゴリズムの計算量

単純なシミュレーション問題なので計算量を求めることは不要。

アルゴリズムの実装

解答ソースコードを2つ挙げていますが,異なるのは「全部取れたか」のチェック部分(とそれに関わる部分)だけです。 p0101-deq_1.cpp の方が行数も少なくスマートですが,特にこれといった違いはありません。 p0101-deq_2.cpp は各データセットに答える部分を bool solve() といった関数に切り分けて, チェック部分で return false; して二重ループを抜けた方が綺麗なコーディングになりますが, main() に押し込んでしまっている場合は goto を使って多重ループを抜けるとそこそこ綺麗に書けます。

フィールドなどの状態を保持する変数は main 関数の外に出して「コーディングの最初から」グローバル変数として宣言しておくと良いでしょう。 後で関数を切り分けた場合などでも簡単に対処できますし,ごちゃごちゃいじった場合の初期化に関わるミスも減ります。

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