← 返回题目列表

AtCoder · joi2016yo_f

F. 大排档

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

配点: 100 点

問題

JOI 您居住的IOI市位于南北方向。 H 剖面,东西方向 W 它具有矩形形状, 它分为H \times W 部分。从北方 i ,从西边 j 第分区 表示为 (i, j) 。目前,IOI 城正在举办一场大型庆典,以纪念正在举办的国际编程大赛。有些区域设有摊位,每个摊位都出售不同类型的糖果。隔间 (1, 1),区画 (H, W) 及其邻近的北、南、东、西区域没有小吃摊。

JOI你是一段 从 (1, 1) 分区 移至 (H, W) 。为了缩短旅行时间,JOI只向东或向南移动。 JOI 你喜欢甜食,所以每次进入车厢时,你都会按顺序进行以下动作。

  • 如果当前区域有卖糖果的摊位,而您还没有购买过,请在该摊位购买糖果。
  • 如果在与北、南、东、西以及当前区域相邻的区域中有出售您尚未购买的糖果的摊位,则这些摊位中 1 致电除一个摊位外的所有摊位的销售人员并购买糖果。

JOI 你不会多次购买同一种糖果。

IOI 鉴于城市的规模、摊位的位置以及每个摊位的糖果价格,JOI 求前往 (1, 1) 分区 移至 (H, W) 旅行时购买糖果的最低总量。 由


入力

输入是 有一条 1 + H 行组成。 在

1 行中,2 整数 H, W (3 \leqq H \leqq 1\,000,3 \leqq W \leqq 1\,000)以空格作为分隔符。这是因为IOI城 表示它分为 H \times W 部分。

续 H 每行有 W 写入一串字符,代表IOI城各个部分的信息。H 行 i 从该行的左侧开始 j 第一个字符 (1 \leqq i \leqq H,1 \leqq j \leqq W) 是一个分区 如果 (i, j) 中没有停顿 . (句号)。如果有摊位 1, 2, \ldots, 9 代表该摊位出售的糖果的价格。

给出 5 在输入数据中,输入 1 ,档位数量为 20 下面。

出力

JOI 口交 (1, 1) 分区 移至 (H, W) 旅行时购买糖果的最低总量 输出为 1 行。 在


入力例 1

5 5
..483
.59.9
3.866
79...
4.8..

出力例 1

20

入出力例 1 中,分区 按 (1, 1),区画 (2, 1),区画 (3, 1),区画 (3, 2),区画 (4, 2),区画 (4, 3),区画 (4, 4),区画 (4, 5),区画 (5, 5) 的顺序移动, (3, 1),区画 (3, 3),区画 (4, 2) 摊位出售的糖果,则您购买的糖果总量将为最少。


入力例 2

12 10
..498522.4
.633527629
54.4621596
634.213458
1924518685
7739539767
276155.3.6
87716372.2
.858877595
7998739511
3438.5852.
568.9319..

出力例 2

63