P3659 [USACO17FEB] Why Did the Cow Cross the Road I G

题目描述

奶牛为什么要过马路?其中一个原因是 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 需要走很长一段路。由于她在路上会感到饥饿,她会在每经过第三个田地时停下来吃草(不包括她的起始田地,但可能包括最终到达的 FJ 家的田地)。有些田地的草比其他田地更茂盛,因此停下来吃草所需的时间取决于她停下的田地。 请帮助 Bessie 确定她到达 FJ 家所需的最少时间。

输入格式

输出格式

说明/提示

这个例子的最优解是向东移动 3 个方格(吃“10”),然后向南移动两次,向西移动一次(吃“5”),最后向南和向东移动到目的地。