← 返回题目列表

AtCoder · joi2013yo_f

F. 纪念品购买计划(礼物)

中文机器翻译题面 查看原题

配点: 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