配点: 100 点
問題
JOI去澳大利亚旅行,游览了各地,终于到了回国的日子。 JOI 现在所在的城镇是他回程航班起飞的国际机场所在的城镇。这个小镇分为北、南、东、西四个部分,每个部分都有道路、纪念品商店、住宅和国际机场。 JOI 从最西北的区域出发,目标是最东南的国际机场。
JOI 您可以从当前所在的区域移动到相邻区域,但无法进入房屋所在的区域。另外,为了赶上您的航班,您应该只移动到您当前所在区域的东部或南部。但是,由于我们还有一些时间, 您最多可以移动到当前所在区域的北区或西区K 次。
JOI 您进入纪念品商店区并为您的日本朋友购买纪念品。 JOI 您仔细研究了纪念品商店,因此您知道可以去哪家纪念品商店以及可以购买多少纪念品。 JOI 编写一个程序来查找您可以购买的纪念品的最大数量。
然而,假设购买纪念品所花费的时间可以忽略不计, 2 如果您多次访问,请仅在第一次访问时购买纪念品。 在
入力
输入是 由 1 + H 行组成。
1 行中,3 整数 给出了 H, W, K (2 \leqq H \leqq 50,2 \leqq W \leqq 50, 1 \leqq K \leqq 3)以空格作为分隔符。 每条
继续 H 行都有 W 写入由字符组成的字符串,表示有关包裹的信息。从北方 i ,从西边 j 第节 (i, j) (1 \leqq i \leqq H,1 \leqq j \leqq W) .i 线
第 j 个字符是分区 (i, j) 是道路或国际机场。 . ,如果是房子,那么 # 。如果是纪念品商店 1,2,\ldots,9 代表可以在纪念品商店购买的纪念品数量。
给定输入数据,可以保证JOI开头的最西北路段是一条道路。另外,JOI也能保证能够到达国际机场。
出力
JOI 一个整数,表示您可以购买的纪念品的最大数量。 输出为 1 行。 在
入力例 1
5 4 2 ...# .#.# .#73 8##. ....
出力例 1
11
入出力例 1 中,JOI是 3 前往海南并路段 在 (4, 1) 的纪念品商店购物后,继续向南行驶。 1 次,向东 向前走 3 次,然后向北 按前进 2 次进行分区 在 (3, 4) 的纪念品商店购物。终于南了 如果您出行 2 次并到达国际机场,则总计 您可以购买 11 纪念品。
入力例 2
4 4 3 .8#9 9.#. .#9. ....
出力例 2
27