問題一覧 > 通常問題

No.611 Day of the Mountain

レベル : / 実行時間制限 : 1ケース 2.017秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 22
作問者 : square1001square1001 / テスター : uwiuwi
1 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$ 行目には, 文字列 $A_i$ が与えられる. $A_i$ の $j$ 文字目が $1$ 以上 $9$ 以下の数字のときこれは区画 $(i, j)$ の歩きにくさの値を表し, '?' のとき区画 $(i, j)$ の歩きにくさがまだ分かっていないことを表す.

出力

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

制限

  • $4HW \leq 1211$.
  • $A_i \ (1 \leq i \leq H)$ は '1' ~ '9' または '?' のみで構成されている $W$ 文字の文字列である.

サンプル

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

この場合 '?' のうちどれかが '1' であればツアーの時間は $6$ 時間となり, このような場合は $9^4 - 8^4 = 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もしくは右上の雲マークをクリックしてアカウントを作成してください。