2003/Contest/会津大会

Problem D : Weather Forecast

問題概要

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

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

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

解法

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

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

審判団からのヒント

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

議論・その他

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

ファイルを添付する

filetadokoro_weather.cpp 543件 [詳細] fileweather.txt 520件 [詳細] filedeadbeef_d.cpp 610件 [詳細] filevertices_TLE2_D3.cpp 503件 [詳細] filevertices_TLE1_D2.cpp 510件 [詳細] filevertices_D.cpp 512件 [詳細] filehirano_weather.cpp 531件 [詳細] filenoda_weather.cpp 596件 [詳細] fileweather.out.txt 486件 [詳細]
[添付ファイル一覧] [全ページの添付ファイル一覧]
アップロード可能最大ファイルサイズは 10,240KB です。

管理者パスワード:

添付ファイル: filetadokoro_weather.cpp 543件 [詳細] fileweather.txt 520件 [詳細] filedeadbeef_d.cpp 610件 [詳細] filevertices_TLE2_D3.cpp 503件 [詳細] filevertices_TLE1_D2.cpp 510件 [詳細] filevertices_D.cpp 512件 [詳細] filehirano_weather.cpp 531件 [詳細] filenoda_weather.cpp 596件 [詳細] fileweather.out.txt 486件 [詳細]

Last-modified: 2009-11-06 (金) 13:26:46 (2995d)