2012年5月9日水曜日

GCJ2012 Round 1B Problem B. 問題紹介

Google Code Jam 2012 Round 1B
Problem B. Tide Goes In, Tide Goes Out 問題紹介

地下の洞窟で潮が満ちてきて… みたいなストーリーがありますが、ようするにパズルゲームだと思うのが手っ取り早いです。
kayak ってナニ? と思ったら画像検索するとイメージしやすいかも。Googleさんは kayak がお好きなようです。(Googleマップで海外への経路を検索すると「カヤックで渡る」という選択肢が出てくる…という話題が一頃あったような)

ルールがたくさんあるのが面倒くさい Problem です…
  • N×M マス(square)のマップを、左上(北西)から右下(南東)まで移動します。
  • square ごとに床と天井の高さが指定されています。
  • ある一定の高さまで水が張っていますが、10cm/秒の速さで水位が下がっていきます(潮が干く)。
  • 水位が下がりはじめてからゴールに到達するまで何秒かかるか求める問題です。
  • 水位が床上 20cm 以上の場合は kayak を使って隣接する square に移動することができます。この場合、移動に 1秒 かかります。床上20cm以上の水位がない場合は、 kayak を押して移動しないといけないので 10秒 かかってしまいます。
    ※移動前の square の床の高さだけで判断できます。移動先での水位は関係ありません。
  • 天井と水面(または床)の間が 50cm 以上あいていないと、その square に入ることができません。別の square へ行くか、水位が下がるのを待つ必要があります。
    • 今いる square の床と移動先の天井(または今いる square の天井と移動先の床)が 50cm に満たない場合、その経路は移動できません。(別の方角からは入れる可能性があります)
    • 床と天井が 50cm 未満の square にはどの方角からも入ることができません。
  • 50cmルールが守られていれば高度の移動は無視できます。10cmの床から9000cmの床に移動することもできます。
  • 左上端からスタートしますが、水位が下がり始める前でも移動することができます。求めるのは「水位が下がりはじめてからの時間」なので、運良く水位が初期状態のままゴールまでたどり着ければ 0.0秒 が答えになります。(Sampleの #4)
  • スタート(左上)からゴール(右下)まで必ず経路があります。

入力データ:
最初の行は問題数 T。以降 T問の問題データが続きます。
問題データの最初の行は3つの整数 HNM です。H は初期状態の水位です。
続く N行は各 square の天井の高さ Cxy です。各行にスペース区切りで M個の値が入っています。
続く N行は各 square の床の高さ Fxy です。天井と同じフォーマットです。
スタート地点(左上)とゴール地点(右下)は必ず天井の高さと床の高さが 50cm以上離れています。また、スタート地点の天井は H(最初の水位)より 50cm以上高くにあります。(スタート地点やゴール地点が50cmルールを守っている、ということです)

データ制限(Small input の場合):
  • 1 ≤ T ≤ 50 (問題数は50問)
  • 1 ≤ N,M ≤ 10 (マップは最大で10×10)
  • 1 ≤ H ≤ 1000 (水位は最大1000cm)
  • 1 ≤ Fxy ≤ Cxy ≤ 1000 (床、天井の高さも最大1000cm)

データ制限(Large input の場合):
  • 1 ≤ T ≤ 50 (問題数は50問)
  • 1 ≤ N,M ≤ 100 (マップは最大で100×100)
  • 1 ≤ H ≤ 10000 (水位は最大10000cm)
  • 1 ≤ Fxy ≤ Cxy ≤ 10000 (床、天井の高さも最大10000cm)

解き方はこちら

0 件のコメント:

コメントを投稿