题目大意:n行m列的木瓜地,每个格子有一定数量的木管,从左上角开始吃,每次只往周围4个方向最多木瓜的地方走,最终走到右下角,共吃得多少个木瓜?
题目描述
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一共吃了多少个木瓜。
输入
* 第2到R+1行: 第i+1行有C个空格隔开的整数,表示第i行的每个格的水果数。也就是F_i1, F_i2, …, F_iC.
输出
样例输入
3 4
3 3 4 5
4 5 3 2
1 7 4 2
样例输出
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扫荡过了)。
解题思路
首先读入数据到a[][],接着从(1, 1)开始吃木瓜,吃完标记为0,再找下一个位置,当右下角a[n][m]的木瓜还没吃,一直吃下去,知道a[n][m]为0,吃完右下角的才停止,最后输出吃的木瓜数量。
如何判断下一个位置在哪?当前位置是(i, j),那么下一个位置从(i+1, j)、(i-1, j)、(i, j+1)、(i, j-1)中选木瓜最多的,为了方便,可以开dx、dy这样的数组,以后8个方向也能够快速写完。