Mysterious Gems 解説
- 問題名:Mysterious Gems
- 出典:Problem A, ACM/ICPC Practice Contest for Japan Domestic, 2006-06-18
- 難易度:☆
- 問題の種類:シミュレーション
- 解法:特になし
- 解答ソースコード:
- OB/OGの会の解説:p0101-obog.pdf
アルゴリズムの概略
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 $