← 返回题目列表

AtCoder · past201912_j

J. 调平

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

警告

在日本标准时间 2019 年 12 月 29 日凌晨 05:00 之前请勿提及此问题。如有违反,可要求赔偿。

考试结束后,您可以向其他人透露您的总分和等级,但仅此而已(例如,您解决了哪些问题)。

问题陈述

有一块长方形的土地,分为一个网格 H \times W 方块与 H 水平行和 W 垂直列。除网格左下角、右下角和右上角的三个方格外,所有方格均未铺砌。广场上铺设了 i从顶部开始的第行和 j左起第 列 (1 \leq i \leq H, 1 \leq j \leq W) 成本 A_{i,j} 日元(日本的货币)。

我们在网格左下角的正方形中有一个对象。你想把它带到右下角​​的方块,然后到右上角的方块。

要携带该物体,您需要将其从一个方格重复移动到与当前占据的方格水平或垂直相邻的另一个方格。在这里,物体经过的所有方格都必须被铺好。一旦正方形被铺好,物体就可以多次穿过该正方形。

找出为您的目标铺平方块所需的最低金额。

约束

  • 2 \leq H, W \leq 50
  • 0 \leq A_{i,j} \leq 100000
  • A_{H,1} = A_{H,W} = A_{1,W} = 0
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

H W
A_{1,1} A_{1,2} \ldots A_{1,W}
A_{2,1} A_{2,2} \ldots A_{2,W}
:
A_{H,1} A_{H,2} \ldots A_{H,W}

输出

打印代表最低金额的整数。


示例输入 1

5 6
9 9 9 9 1 0
9 9 9 9 1 9
9 9 9 1 1 1
9 1 1 1 9 1
0 1 9 9 9 0

示例输出 1

10

最好铺好所有方格,成本 1 日元铺路。


示例输入 2

10 10
1 2 265 1544 0 1548 4334 9846 58 0
21 0 50 44 2 388 5 0 0 4
170 0 2 1 54 1379 50 3 41 0
310 0 1 0 2163 0 226 26 3 12
151 33 0 9 0 0 0 36 365 2286
0 3 12 3 9 317 645 100 21 4
52 1 569 0 144 0 6 202 25 0
8869 19 2058 1948 1252 1002 7 1750 0 5
0 3 8 29 2 4403 0 0 0 5
0 17 93 9367 159 6 1 216 0 0

示例输出 2

246