問題一覧 > 通常問題

No.611 Day of the Mountain

レベル : / 実行時間制限 : 1ケース 2.017秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 26
作問者 : square1001 / テスター : uwi
2 ProblemId : 1859 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2017-12-11 00:16:08

背景

12 月 11 日は "International Mountain Day" - これは山の日の国際版であるので、これに関して問題を出す。

問題文

あなたはある山岳地帯のツアーを企画しようとしている. この山岳地帯は南北方向に H マイル, 東西方向に W マイルの長方形の形をしている. また, 区画 (i,j) を, 北から i マイル ～ i+1 マイル, 西から j マイル ～ j+1 マイルの位置にある部分とする.
あなたは次の条件で, ツアーのルートを決めたい.

  • スタート地点を駐車場のある区画 (1,1), ゴール地点を山頂のある区画 (H,W) にする.
  • ツアー中に遭難するのをできるだけ避けたいので, 東方向に 1 区画, あるいは南方向に 1 区画の移動を何回か行うことでスタートからゴールまで移動することにする.
  • ツアーにかかる時間は (通ったマスの「歩きにくさ (1以上9以下の整数)」の合計としてありうる値の中で最小の値) である.
しかし, 歩きにくさの調査がまだ全部終わっていないため、いくつかのマスの歩きにくさは分かっていない. そこで, ツアーにかかる時間だけでも推測しようと思ったあなたは, 次の情報から分析しようと思った.
  1. 歩きにくさがまだ分かっていないマスの歩きにくさを全部 1 にした場合のツアーにかかる時間 T (時間)
  2. ツアーにかかる時間が T 時間であるような, マップ (歩きにくさの割り当て方) の種類数 X
そのとき, T, X を求めるプログラムを作れ. ただし, X の値は非常に大きくなることがあるので, X の代わりに X を 201,712,111 で割った余りを求めなさい.

入力

  • 1 行目には, 整数 H と W が与えられる.
  • i+1 行目には, 文字列 Ai が与えられる. Ai の j 文字目が 1 以上 9 以下の数字のときこれは区画 (i,j) の歩きにくさの値を表し, '?' のとき区画 (i,j) の歩きにくさがまだ分かっていないことを表す.

出力

  • 1 行目に T の値を出力せよ.
  • 2 行目に X を 201,712,111 で割った余りを出力せよ.

制限

  • 4HW≤1211.
  • Ai (1≤i≤H) は '1' ～ '9' または '?' のみで構成されている W 文字の文字列である.

サンプル

サンプル1
入力
3 4
1111
????
1111
出力
6
2465

この場合 '?' のうちどれかが '1' であればツアーの時間は 6 時間となり, このような場合は 94−84=2465 通りある.

サンプル2
入力
3 4
3333
????
3333
出力
10
1

次のような場合のみにおいてツアーの時間 10 時間が達成できる. 

3333
1111
3333

サンプル3
入力
6 6
2?17??
?1211?
??2?17
1211??
?2?17?
??1211
出力
13
24869728

ツアーの時間は最小で 13 時間になる. また, このようなマップの状態は 62,757,336,249 通りあり, これを 201,712,111 で割った余りである 24,869,728 を出力する.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。