软件测试 捡胡萝卜

给定一个n * m 的矩阵 carrot , carrot[i][j] 表示(i, j) 坐标上的胡萝卜数量。从矩阵的中心点出发，每一次移动都朝着四个方向中胡萝卜数量最多的方向移动，保证移动方向唯一。返回你可以得到的胡萝卜数量。

• n 和 m 的长度范围是: [1, 300]
• carrot[i][j] 的取值范围是: [1, 20000]
• 中心点是向下取整, 例如n = 4, m = 4, start point 是 (1, 1)
• 如果格子四周都没有胡萝卜则停止移动

样例

示例 1:

输入:
carrot = 
[[5, 7, 6, 3],
[2,  4, 8, 12],
[3, 5, 10, 7],
[4, 16, 4, 17]]
输出: 
83
解释：
起点坐标是(1, 1), 移动路线是：4 -> 8 -> 12 -> 7 -> 17 -> 4 -> 16 -> 5 -> 10
           

题目难度：一般

题目来源：LintCode 炼码

示例 2:

输入:
carrot = 
[[5, 3, 7, 1, 7],
 [4, 6, 5, 2, 8],
 [2, 1, 1, 4, 6]]
 输出: 
 30
 解释：
 起始点是 (1, 2), 移动路线是： 5 -> 7 -> 3 -> 6 -> 4 -> 5