- 标签 USACO 2017 高性能
- 难度 提高+/省选-
- 时空限制 1s / 128MB
Why did the cow cross the road? Well, one reason is that Farmer John's farm simply has a lot of roads, making it impossible for his cows to travel around without crossing many of them.
FJ's farm is arranged as an $N \times N$ square grid of fields ($3 \leq N \leq 100$), with a set of $N-1$ north-south roads and $N-1$ east-west roads running through the interior of the farm serving as dividers between the fields. A tall fence runs around the external perimeter, preventing cows from leaving the farm. Bessie the cow can move freely from any field to any other adjacent field (north, east, south, or west), as long as she carefully looks both ways before crossing the road separating the two fields. It takes her $T$ units of time to cross a road ($0 \leq T \leq 1,000,000$).
FJ的牧场可以看作是一块 $N\times N$ 的田地（$3\le N\le 100$），$N-1$ 条南北向的道路和 $N-1$ 条东西向的道路贯穿整个牧场，同时是每块田野的分界线。牧场的最外面是一圈高大的栅栏以防止奶牛离开牧场。Bessie只要穿过分离两块田野的道路，就可以从任何田野移动到与其相邻的田野里去（北，东，南或西）。当然，Bessie穿过每一条马路都是需要$T$ 时间的。（$0\le T\le 1,000,000$）
One day, FJ invites Bessie to visit his house for a friendly game of chess. Bessie starts out in the north-west corner field and FJ's house is in the south-east corner field, so Bessie has quite a walk ahead of her. Since she gets hungry along the way, she stops at every third field she visits to eat grass (not including her starting field, but including possibly the final field in which FJ's house resides). Some fields are grassier than others, so the amount of time required for stopping to eat depends on the field in which she stops.
Please help Bessie determine the minimum amount of time it will take to reach FJ's house.
The first line of input contains $N$ and $T$. The next $N$ lines each contain $N$ positive integers (each at most 100,000) describing the amount of time required to eat grass in each field. The first number of the first line is the north-west corner.
接下来 $N$ 行，每行 $N$ 个数表示每块田野Bessie需要停留的时间（每块最多不超过$100,000$），第一行的第一块田野是牧场的西北角输出格式：
Print the minimum amount of time required for Bessie to travel to FJ's house.
The optimal solution for this example involves moving east 3 squares (eating the "10"), then moving south twice and west once (eating the "5"), and finally moving south and east to the goal.