問題文
休息后,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