【每日一题20220921】 捡胡萝卜

给定一个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
from typing import (
    List,
)


class Solution:
    """
    @param carrot: an integer matrix
    @return: Return the number of steps that can be moved.
    """

    def pick_carrots(self, carrot: List[List[int]]) -> int:
        # write your code here
        l = len(carrot) - 1
        w = len(carrot[0]) - 1
        point_l = l // 2
        point_w = w // 2
        carrot_count = carrot[point_l][point_w]
        while True:
            carrot_dic = {}
            carrot[point_l][point_w] = 0
            four_points = [(point_l - 1, point_w), (point_l + 1, point_w), (point_l, point_w - 1),
                           (point_l, point_w + 1)]
            for i in four_points:
                if 0 <= i[0] <= l and 0 <= i[1] <= w:
                    carrot_num = carrot[i[0]][i[1]]
                    carrot_dic[carrot_num] = (i[0], i[1])
            if (m := max(carrot_dic.keys())) > 0:
                carrot_count += m
                tuple_num = carrot_dic[m]
                point_l = tuple_num[0]
                point_w = tuple_num[1]
            else:
                break
        return carrot_count
func PickCarrots(carrot [][]int) int {
	i, j := getCenterPoint(carrot)
	res := carrot[i][j]
	carrot[i][j] = 0
	for {
		var tmp int
		var k int //1 上 2 下 3 左 4右
        if j-1 >= 0 &&  carrot[i][j-1]-tmp > 0 {
			tmp = carrot[i][j-1]
			k = 1
		}
		if j+1 < len(carrot[0]) && carrot[i][j+1]-tmp > 0 {
			tmp = carrot[i][j+1]
			k = 2
		}
		if i-1 >= 0 &&  carrot[i-1][j]-tmp > 0 {
			tmp = carrot[i-1][j]
			k = 3
		}
		if i+1 < len(carrot) && carrot[i+1][j]-tmp > 0 {
			tmp = carrot[i+1][j]
			k = 4
		}

		if k == 1 {
			j--
		} else if k == 2 {
			j++
		} else if k == 3 {
			i--
		} else if k == 4 {
			i++
		} else {
			break
		}
		carrot[i][j] = 0
		res += tmp
	}
	return res
}

func getCenterPoint(carrot [][]int) (x, y int) {
	return (len(carrot) - 1) / 2, (len(carrot[0]) - 1) / 2
}
关闭