USACO/papaya

第四题: 木瓜林 [80分] [Rob Kolstad, 2009]

问题描述

Bessie不小心游荡出Farmer John的田地，而走进了相邻的农民的地。她举起一个木瓜，木瓜对奶牛来说可是不可多得得美味。这个木瓜林像一般的威斯康星州的田地一样被分割成一个R行C列的网格(1 <= R <= 40, 1 <= C <= 40)。Bessie可以从一个格沿着一条跟X轴或Y轴平行的直线走到邻接的令一个格。Bessie发现一开始她自己在木瓜林的(1,1)，也就是第一行第一列慢悠悠地咀嚼着木瓜。

Bessie总是用她最信赖地双筒望远镜去数每一个邻接的格的低挂着的木瓜的数目。然后她就游荡到那个有最多没有被吃掉的木瓜的邻接的格子（保证这样的格子只有一个）。

按照这种移动方法，最终Bessie总是会在(R,C)停止然后吃掉那里的木瓜。

给定这个木瓜林的大小及每个格的木瓜数F_ij(1 <= F_ij <= 100), 要求Bessie一共吃了多少个木瓜。

分值: 80

题目名称: papaya

输入格式:

• 第一行: 两个空格隔开的整数R和C.

• 第2到R+1行: 第i+1行有C个空格隔开的整数，表示第i行的每个格的水果数。也就是F_i1, F_i2, ..., F_iC.

样例输入 (文件 papaya.in):

3 4
3 3 4 5
4 5 3 2
1 7 4 2

输入细节:

三行四列。Bessie起始于左上角的"3"。

输出格式:

• 第一行: 一个单独的整数，表示到Bessie吃完右下角(R,C)的木瓜回到牛棚的时候为止，一共在木瓜林吃掉了多少个木瓜。

样例输出 (文件 papaya.out):

39

输出格式:

Bessie按照下图数字旁边的字母的顺序吃掉木瓜。

     (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)

她吃了39个木瓜，剩下4个没有吃（也就是说除了2个格幸免于难，剩下的格子都被Bessie扫荡过了）。

原题

Problem 4: Papaya Jungle [80 points] [Rob Kolstad, 2009]

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.

POINTS: 80

PROBLEM NAME: papaya

INPUT FORMAT:

* 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

SAMPLE INPUT (file papaya.in):

3 4
3 3 4 5
4 5 3 2
1 7 4 2

INPUT DETAILS:

Three rows; four columns. Bessie starts in upper left corner at the '3'.

OUTPUT FORMAT:

* 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).

SAMPLE OUTPUT (file papaya.out):

39

OUTPUT DETAILS:

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).