- 题目提供者 FarmerJohn2
- 评测方式 云端评测
- 标签 USACO 2009
- 难度 普及-
- 时空限制 1000ms / 128MB
Bessie has wandered off the farm into the adjoining farmer's land. He raises delicious papaya fruit, which is a delicacy for cows. The papaya jungle is partitioned into a grid of squares with R rows and C columns (1 <= R <= 40, 1 <= C <= 40), as is popular in Wisconsin. Bessie can travel from a given square to any existing adjacent square whose route is parallel to the X or Y axis. So in the
following diagram, if Bessie is at the square labeled 'B', she can travel to any of the squares labeled 'T':
.T. TBT .T. Bessie always starts out by munching the papayas in square
(row=1,col=1). After she's done with one square, Bessie always uses her trusty binoculars to count the low-hanging fruit in each of the adjacent squares. She then always moves to the square with the most visible uneaten fruit (a square that happily is always unique).
Sooner or later, following this rule, Bessie always ends up in square (R,C) and eats the fruit there.
Given the dimensions of the papaya jungle and the amount of fruit F_ij in each square (1 <= F_ij <= 100), determine the total number of fruit Bessie consumes for a given papaya jungle.
Bessie不小心游荡出Farmer John的田地，而走进了相邻的农民的地里。她举起一个木瓜，木瓜对奶牛来说可是不可多得得美味。这个木瓜林像一般的威斯康星州的田地一样被分割成一个R行C列的网格(1 <= R <= 40, 1 <= C <= 40)。Bessie可以从一个格沿着一条跟X轴或Y轴平行的直线走到邻接的另一个格。Bessie发现一开始她自己在木瓜林的(1,1)，也就是第一行第一列慢悠悠地咀嚼着木瓜。
给定这个木瓜林的大小及每个格的木瓜数F_ij(1 <= F_ij <= 100), 要求Bessie一共吃了多少个木瓜。
* Line 1: Two space-separated integers: R and C
* Lines 2..R+1: Line i+1 describes row i of the jungle with C
space-separated integers that tell how many fruit are in each square: F_i1, F_i2, ..., F_iC输出格式：
* Line 1: A single integer that is the total number of papayas that Bessie eats by the time she finishes off the papayas at the barn in the lower right corner at coordinate (R,C).
Three rows; four columns. Bessie starts in upper left corner at the '3'.
Bessie eats the papayas in the order given by the letters next to the numbers below:
(1,1) ---> (1,C)
(1,1) 3a 3 4g 5h (1,C)
| 4b 5c 3f 2i |
(R,1) 1 7d 4e 2j (R,C)
(R,1) ---> (R,C)
She declines to eat 4 of the papayas but consumes 39 (visiting all but two squares of the grid).