Problem D : Weather Forecast †問題概要 †4x4マスの国土に、2x2マスの雨雲が浮かんでいる。あなたは雨雲を縦または横に毎日0〜2マスずつ動かすことができる。なぜなら神だから。ただし、雨雲が国土の外にはみだすような移動はできない。 雨雲に覆われた土地には雨が降るが、市場や祭が開かれている土地(毎日変わる)には雨を降らせてはならない。また、7日以上雨の降らない土地があると干ばつが起こり神の威厳が損なわれるので、どのマスも少なくとも6日に一度は雨を降らせる必要がある。 以上の条件を満たすように雨雲を動かすことができるかどうかを調べる。 解法 †探索。同じ状態を複数回調べないようにする。STL なら、調べた状態を set に放りこむのがお手軽。 可能な手順をひとつ見つければよいので深さ優先で調べるのが最適だろうが、幅優先でも間に合った。(菊地) 審判団からのヒント †干ばつチェックは、国土の四隅だけを調べればよい。 議論・その他 †
ファイルを添付する †tadokoro_weather.cpp 1228件 [詳細] weather.txt 929件 [詳細] deadbeef_d.cpp 1083件 [詳細] vertices_TLE2_D3.cpp 869件 [詳細] vertices_TLE1_D2.cpp 879件 [詳細] vertices_D.cpp 894件 [詳細] hirano_weather.cpp 1312件 [詳細] noda_weather.cpp 1766件 [詳細] weather.out.txt 840件 [詳細] |