2003/Contest/会津大会

Problem D : Weather Forecast †

問題概要 †

4x4マスの国土に、2x2マスの雨雲が浮かんでいる。あなたは雨雲を縦または横に毎日0〜2マスずつ動かすことができる。なぜなら神だから。ただし、雨雲が国土の外にはみだすような移動はできない。

雨雲に覆われた土地には雨が降るが、市場や祭が開かれている土地(毎日変わる)には雨を降らせてはならない。また、7日以上雨の降らない土地があると干ばつが起こり神の威厳が損なわれるので、どのマスも少なくとも6日に一度は雨を降らせる必要がある。

以上の条件を満たすように雨雲を動かすことができるかどうかを調べる。

解法 †

探索。同じ状態を複数回調べないようにする。STL なら、調べた状態を set に放りこむのがお手軽。

可能な手順をひとつ見つければよいので深さ優先で調べるのが最適だろうが、幅優先でも間に合った。(菊地)

審判団からのヒント †

干ばつチェックは、国土の四隅だけを調べればよい。

議論・その他 †

• 深さ優先は同じ状態を複数回調べないようにするロジックを組むのが面倒。グローバルな set 型の変数でも用意すればいいのかもしれないが。ちなみに、干ばつチェックのほうは私はコンテスト中に気付きました（泉）

---

ファイルを添付する †

tadokoro_weather.cpp 1366件 [詳細] weather.txt 1030件 [詳細] deadbeef_d.cpp 1193件 [詳細] vertices_TLE2_D3.cpp 946件 [詳細] vertices_TLE1_D2.cpp 983件 [詳細] vertices_D.cpp 1019件 [詳細] hirano_weather.cpp 1463件 [詳細] noda_weather.cpp 1987件 [詳細] weather.out.txt 976件 [詳細]

[添付ファイル一覧] [全ページの添付ファイル一覧]
アップロード可能最大ファイルサイズは 10,240KB です。
添付ファイル:
管理者パスワード: Rename the filename to: