/ 
Time Limit: 1 sec / Memory Limit: 64 MB
問題文
休憩を終えたjoisinoお姉ちゃんは、偶然知り合った冒険者の人とともに、ダンジョンに潜ることにした。
順調な道のりだったが、途中で事故が起き、急いで安全地帯まで向かう必要に迫られた。
このダンジョンは、全ての階層で、南北にR個、東西にC個、全部でR*C個の部屋が格子状に並んでいる。
joisinoお姉ちゃんたちは現在いる階層の、最も北西の部屋にいる。
安全地帯は、現在の階層からN-1回降りた階層の、最も南東の部屋である。
安全地帯の存在する階層以外の各階層にはいくつか穴が存在する。
穴は部屋の中にあり、穴に落ちることで、一つ下の階層に降りることができる。
この時、穴のあった場所が、北西の部屋から、東にx 南にy 進んだ部屋だった場合、落ちた先の部屋も、北西の部屋から東にx 南にy 進んだ部屋である。
なお、落ちた先の部屋にも穴があるということはない。
また、穴のある部屋に入ったときは、必ず落ちなくてはならない。
それぞれの部屋には、危険度というものがある。
この危険度が高ければ高いほど、その部屋を通る危険が大きいことを表す。
穴のある部屋の危険度は0であるが、落ちたあとの部屋の危険度は考慮するものとする。
なお、現在joisinoお姉ちゃんがいる部屋、安全地帯の部屋の危険度は0である。
joisinoお姉ちゃんたちは、できるだけ危険を避けつつ、安全地帯まで移動したい。
そのために、最短経路(西や北に移動しないようにした道順)の中で、通る部屋の危険度の合計が最小となるルートで進むことにした。
優秀なプログラマーであるjoisinoお姉ちゃんは、そのようなルートで進んだ時の、危険度の合計を求めるプログラムを作成することにした。
入力
入力は以下の形式で標準入力から与えられる。
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