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).
[Vietnamese Translation]
Bessie đã lơ đễnh đi khỏi nông trang vào đến mảnh đất của nông dân kề bên.
Anh ấy đang trồng quả đu đủ rất ngon, mà là một đồ ngon cho những con bò.
Rừng rậm đu đủ bị phân chia vào trong một hệ thống lưới của ô vuông với
R hàng và C cột (1 <= R <= 40 1 <= C <= 40), được ưa chuộng ở Wisconsin.
Bessie có thể đi từ một ô vuông được cho để bất cứ ô vuông liền kề mà
tuyến đường của nó song song tới trục X hoặc Y. Bessie phát hiện chính
cô ta trong ô vuông (row=1,col=1) đang nhai đu đủ ở đó.
Bessie luôn luôn sử dụng ống nhòm đáng tin cậy của cô ấy để đếm số
trái cây dưới thấp trong mỗi ô vuông liền kề. Sau đó, cô ta luôn luôn
di chuyển đến các ô vuông với trái cây chưa được ăn là nhiều nhất
(Thật may, ô vuông đó luôn luôn là duy nhất).
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).
Sớm hay muộn hơn, theo quy tắc này, Bessie luôn luôn kết thúc tại ô vuông (R, C)
và ăn những trái cây ở đó.
Cho các kích thước của rừng đu đủ và số lượng trái cây F_ij trong từng ô vuông
(1 <= F_ij <= 100), hãy xác định tổng số trái cây Bessie ăn cho một rừng đu đủ đã cho.
ĐIỂM: 80
TÊN BÀI: papaya
KHUÔN DẠNG DỮ LIỆU VÀO:
* Dòng 1: Hai số nguyên được cách nhau bởi dấu trống: R và C
* Các dòng 2..R+1: Dòng i+1 miêu tả dòng i của rừng với C số nguyên
được cách nhau bởi dấu trống mà nói cho biết bao nhiêu trái
cây như thế nào nằm trong mỗi ô vuông: F_i1, F_i2, ..., F_iC
DỮ LIỆU VÀO MẪU (tệp tin papaya.in):
3 4
3 3 4 5
4 5 3 2
1 7 4 2
CHI TIẾT DỮ LIỆU VÀO:
Ba hàng; bốn cột. Bessie bắt đầu ở góc trên bên trái tại '3'.
KHUÔN DẠNG KẾT QUẢ:
* Dòng 1: Một số nguyên duy nhất là tổng số của đu đủ mà
Bessie ăn tại thời gian kết thúc mà cô hoàn thành ở trang trại
tại ở góc dưới bên phải với tọa độ (R, C).
KẾT QUẢ MẪU (tệp tin papaya.out):
39
CHI TIẾT KẾT QUẢ:
Bessie ăn các quả đủ đu theo thứ tự được đưa ra bởi các chữ cái bên cạnh
con số dưới đây:
(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)
Cô ấy từ chối ăn 4 quả đủ đu nhưng ăn 39 quả (ghé thăm tất cả,
nhưng hai ô vuông của lưới).
[Chinese Translation]
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掃
蕩過了）。