Skip to content

1195: 方格图

题目

题目描述

有一幅$n*n$的方格图,每个点上有一个值 $a_{i,j}$。

从$(1,1)$出发,走到$(n,n)$,只能走上下左右。

每走一步花费$t$,每走三步需要花费走完三步后到达格子的值。

求最小花费的值。

输入格式

第一行两个整数 $n$ 和 $t$。

接下来 $n$ 行,每行 $n$ 个数,代表方格图上的值。

输出格式

输出一行一个整数,表示最小花费的值。

样例输入

4 2

30 92 36 10

38 85 60 16

41 13 5 68

20 97 13 80

样例输出

31

提示

对于样例,先向右走三步(额外花费“10”),再向下走两步,又向左走了一步(额外花费“5”),最后向下走一步,再向右走一步到达终点,总共时间是15(额外花费)+16=31

数据范围

对于 $100\%$的数据,$3\le n \le 100,0 \le t \le 1000000,1\le a_{i,j} \le 100000$。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!