軟體測試 撿胡蘿蔔

給定一個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