← 返回题目列表

AtCoder · tkppc2015_d

D. 支持者

中文机器翻译题面 查看原题
我做了重新判断。

問題文

休息后,Joisino姐姐决定和她偶然遇到的冒险家一起潜入地下城。
旅​​途很顺利,但途中发生了意外,我们被迫赶往安全地带。

这个地牢位于所有楼层的南北。R件,从东到西C件,总计R*C房间排列成网格状。
joisino姐妹在她们当前所在楼层的最西北的房间里。
安全区从当前级别开始。N-1这是你下降的楼层最东南的房间。

除了安全区所在的那一层外,每一层都有几个洞。
房间里有一个洞,掉进洞里就可以下到下一层。
此时,洞口从西北房间移到了东边。x 向南y 如果房间是高级的,你掉进去的房间也会是从西北房间到东边。x 向南y 这是一个高级房间。
此外,你掉进去的房间里没有洞。
另外,如果你进入一个有洞的房间,你必须从里面掉下去。

每个房间都有一定的危险级别。
危险程度越高,穿过那个房间的危险性就越大。
有洞的房间有多危险?0但是必须考虑跌倒后房间内的危险程度。
Joisino Onee当前所在房间和安全区房间的危险等级为0。

joisino女孩想要移动到安全区,同时尽可能避免危险。
出于这个原因,我决定走最短的路线(避免向西或向北移动的路线),以尽量减少我经过的房间的总危险。
Joisino-nee 是一位优秀的程序员,她决定创建一个程序来计算沿着这样的路线前进时的总风险级别。


入力

输入是按以下格式从标准输入给出的。

N R C
S_1
S_2
:
S_{N*R}
  • 1线显示要经过的层数。N(2≦N≦100)和一个指示层次结构大小的整数R(2≦R≦100)和 按字典顺序比较C(2≦C≦100)用空格分隔。
  • 2从线N*R行中, 代表第K*R+1从线R行包含当前层次结构中的信息。K(0≦K≦N-1)写入有关您下降到的级别的信息。 这个 写入字符串R行i长度C。 这个字符串是 由最多H和 还给出了0减去9的字符组成。 第 j 个字符是H,那么就是从西北房间向东。j-1 向南i-1表示高级房间有洞。 第 j 个字符是0,那么就是从西北房间向东。j-1 向南i-1表示您进入的房间是起点或目标点。 第 j 个字符是 如果是1减去9之间的数字,则从西北房间到东边。j-1 向南i-1表示高级房间的危险等级是该数字。
  • 对于所有输入,保证至少有一条通往安全区的路线。

配点

此题没有部分分。如果你回答正确60点。

出力

在一行中输出总风险级别的最小值。
另外,在输出末尾放置一个换行符。


入力例1

3 3 3
06H
H14
257
337
15H
2H8
829
653
470

出力例1

9
  • 通过向南→落入洞→东→东→落入洞→南,可以将总风险降到最低。

入力例2

2 5 3
013
871
7HH
163
92H
959
248
792
447
550

出力例2

14