2000元阿里云代金券免费领取，2核4G云服务器仅664元/3年，新老用户都有优惠，立即抢购>>>
阿里云采购季（云主机223元/3年）活动入口：请点击进入>>>，
阿里云学生服务器（9.5元/月）购买入口：请点击进入>>>，
描述
给定一个n * m 的矩阵 carrot, carroti 表示(i, j) 坐标上的胡萝卜数量。
从矩阵的中心点出发，每一次移动都朝着四个方向中胡萝卜数量最多的方向移动，保证移动方向唯一。
返回你可以得到的胡萝卜数量。
- n 和 m 的长度范围是: [1, 300]
- carroti 的取值范围是: [1, 20000]
- 中心点是向下取整, 例如n = 4, m = 4, start point 是 (1, 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样例2
示例 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算法：模拟
解题思路
模拟捡胡萝卜的过程，记录答案。
复杂度分析
时间复杂度：O(n*m)
n为矩阵长度，m为矩阵宽度。
空间复杂度：O(n*m)
n为矩阵长度，m为矩阵宽度。
源代码
public class Solution {
/**
* @param carrot: an integer matrix
* @return: Return the number of steps that can be moved.
*/
public int PickCarrots(int[][] carrot) {
int row = carrot.length, col = carrot[0].length, step = 0;
int x = (row + 1) / 2 - 1, y = (col + 1) / 2 - 1;
int answer = carrot[x][y];
int[] x_dir = new int[]{0, 0, 1, -1};
int[] y_dir = new int[]{1, -1, 0, 0};
int[][] visited = new int[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
visited[i][j] = 0;
}
}
visited[x][y] = 1;
while (step <= row * col - 1) {
int move_dir = -1, move_max = -1;
for (int i = 0; i < 4; i++) {
int temp_x = x + x_dir[i];
int temp_y = y + y_dir[i];
if (temp_x >= 0 && temp_x < row && temp_y >= 0 && temp_y < col && visited[temp_x][temp_y] == 0) {
if (carrot[temp_x][temp_y] > move_max) {
move_max = carrot[temp_x][temp_y];
move_dir = i;
}
}
}
if (move_dir == -1) {
break;
}
x += x_dir[move_dir];
y += y_dir[move_dir];
visited[x][y] = 1;
answer += carrot[x][y];
step += 1;
}
return answer;
}
}更多题解参考：九章官网solution
