Why Did the Cow Cross the Road

题目描述

奶牛为什么要过马路？嗯，其中一个原因是 Farmer John 的农场里道路实在太多，导致奶牛在农场里走来走去时不可避免地要穿过许多道路。 FJ 的农场被布置成一个 $N \times N$ 的正方形网格田地（$3 \leq N \leq 100$）。农场内部有 $N-1$ 条南北向道路和 $N-1$ 条东西向道路，它们穿过农场内部，用作田地之间的分隔线。农场外部边界有一圈高高的围栏，阻止奶牛离开农场。奶牛 Bessie 可以从任意一个田地自由移动到任意一个相邻田地（北、东、南或西），只要她在穿过分隔两块田地的道路前小心地左右观察。她穿过一条道路需要 $T$ 个时间单位（$0 \leq T \leq 1,000,000$）。 有一天，FJ 邀请 Bessie 去他家下一盘友好的国际象棋。Bessie 从西北角的田地出发，而 FJ 的房子位于东南角的田地，因此 Bessie 需要走很长一段路。由于她一路上会饿，她会在所访问的每第 3 块田地停下来吃草（不包括起始田地，但可能包括最终包含 FJ 房子的田地）。有些田地草更茂盛，因此停下来吃草所需的时间取决于她停下的田地。请帮助 Bessie 确定到达 FJ 家所需的最少时间。

输入格式

第一行输入包含 $N$ 和 $T$。接下来的 $N$ 行每行包含 $N$ 个正整数（每个最多为 100,000），描述在每块田地吃草所需的时间。第一行的第一个数字对应西北角。

输出格式

输出 Bessie 到达 FJ 家所需的最少时间。

4 2
30 92 36 10
38 85 60 16
41 13 5 68
20 97 13 80

31

提示

该样例的最优解是先向东移动 3 格（吃“10”），然后向南移动 2 次并向西移动 1 次（吃“5”），最后向南并向东移动到达终点。 题目来源：Brian Dean

标签: USACO|2017|Gold

来源

USACO|2017|Gold