[leetcode/lintcode 题解] 算法面试真题详解：捡胡萝卜

描述
给定一个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