AT_past201912_j.地ならし

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个 $h$ 行 $w$ 列的网格图，记第 $i$ 行第 $j$ 列上的数为 $a_{i,j}$ 。

有一个人，要从左下角的格子出发，到右上角和右下角的格子去。他每一次可以到上下左右相邻的四个格子中已经铺好地砖的格子中去。为了这个目标，他必须在一些网格中铺设地砖，第 $i$ 行第 $j$ 列的网格铺设地砖的成本即为 $a_{i,j}$ 。铺完地砖的格子可任意移动。

请求出他可能花费的最小成本。

输入格式

第一行为两个整数 $h$ 和 $w$ 。

接下来是一个 $h$ 行 $w$ 列的方阵，其中第 $i$ 行第 $j$ 列的数值为 $a_{i,j}$ 。

输出格式

输出他所需花费的最小成本。

数据规模与约定

$2 \le h,w \le 50$ ， $0 \le a_{i,j} \le 100000$ ， $a_{h,1}=a_{h,w}=a_{1,w}=0$ ，输入数值均为整数。

输入输出样例

输入#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

输入#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

输入解题思路，AI测评打分。不知道怎么写?

首页