【每日一题20220921】 捡胡萝卜

兴趣爱好交流 每日一题
1

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

题目难度：一般
题目来源：https://www.lintcode.com/problem/1896/?showListFe=true&page=1&problemTypeId=2&pageSize=50

示例 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
2 
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
3 
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
}
4 
def pick_carrots(carrot: List[List[int]]) -> int:
    rows = len(carrot)
    cols = len(carrot[0])
    start_port = (rows//2-1 if rows%2==0 else rows//2,cols//2-1 if cols%2==0 else cols//2)
    #右、下、上、左
    directions=[lambda x,y:(x,y+1),lambda x,y:(x+1,y),lambda x,y:(x-1,y),lambda x,y:(x,y-1)]
    res = carrot[start_port[0]][start_port[1]]
    carrot[start_port[0]][start_port[1]] = -1
    while start_port:
        max_num = 0
        next_place = None
        for i in directions:
            cur_place = i(*start_port)
            if 0<=cur_place[0]<rows and 0<=cur_place[1]<cols and carrot[cur_place[0]][cur_place[1]]>max_num and carrot[cur_place[0]][cur_place[1]] != -1:
                max_num = carrot[cur_place[0]][cur_place[1]]
                next_place=cur_place
        res += max_num
        if  next_place:
            carrot[next_place[0]][next_place[1]] = -1
        start_port = next_place
    return res
5 
def solution(carrot: list) -> int:
    n = len(carrot) - 1
    m = len(carrot[1]) - 1
    sum_num = (n + 1) * (m + 1)
    i = n // 2
    j = m // 2
    final_road_list = [carrot[i][j]]
    for num in range(0, sum_num):
        road_list = []
        if n >= i - 1 >= 0 and m >= j >= 0:
            road_list.append(carrot[i - 1][j])
        if n >= i + 1 >= 0 and m >= j >= 0:
            road_list.append(carrot[i + 1][j])
        if n >= i >= 0 and m >= j - 1 >= 0:
            road_list.append(carrot[i][j - 1])
        if n >= i >= 0 and m >= j + 1 >= 0:
            road_list.append(carrot[i][j + 1])
        if max(road_list) == 0:
            break
        if n >= i - 1 >= 0 and carrot[i - 1][j] == max(road_list):
            carrot[i][j] = 0
            i = i - 1
            final_road_list.append(carrot[i][j])
        elif n >= i + 1 >= 0 and carrot[i + 1][j] == max(road_list):
            carrot[i][j] = 0
            i = i + 1
            final_road_list.append(carrot[i][j])
        elif m >= j - 1 >= 0 and carrot[i][j - 1] == max(road_list):
            carrot[i][j] = 0
            j = j - 1
            final_road_list.append(carrot[i][j])
        elif m >= j + 1 >= 0 and carrot[i][j + 1] == max(road_list):
            carrot[i][j] = 0
            j = j + 1
            final_road_list.append(carrot[i][j])
    return sum(final_road_list)


carrot = [[5, 7, 6, 3],
          [2, 4, 8, 12],
          [3, 5, 10, 7],
          [4, 16, 4, 17]]
assert solution(carrot) == 83
carrot = [[5, 3, 7, 1, 7],
          [4, 6, 5, 2, 8],
          [2, 1, 1, 4, 6]]
assert solution(carrot) == 30
6 
def move(carrot: list) -> list:
    max_x = len(carrot) - 1
    max_y = len(carrot[0]) - 1
    point = [max_x // 2, max_y // 2]
    max_num = carrot[point[0]][point[1]]
    while True:
        ls = [[point[0] - 1, point[1]], [point[0] + 1, point[1]], [point[0], point[1] - 1], [point[0], point[1] + 1]]
        ls2 = {}
        for i in ls:
            if 0 <= i[0] <= max_x and 0 <= i[1] <= max_y and carrot[i[0]][i[1]] != -1:
                ls2[str(i)] = carrot[i[0]][i[1]]
        if len(ls2) > 0:
            a = sorted(ls2.items(), key=lambda x: x[1], reverse=True)
            max_num += a[0][1]
            carrot[point[0]][point[1]] = -1
            point = eval(a[0][0])
        else:
            break
    return max_num


if __name__ == '__main__':
    carrot = [[5, 3, 7, 1, 7],
              [4, 6, 5, 2, 8],
              [2, 1, 1, 4, 6]]
    carrot1 = [[5, 7, 6, 3],
               [2, 4, 8, 12],
               [3, 5, 10, 7],
               [4, 16, 4, 17]]
    assert move(carrot) == 30
    assert move(carrot1) == 83
7 
def solution(carrot: list) -> int:
    def add_remove(i:int,j:int):
        res_list.append(carrot[i][j])
        carrot[i][j] = 'x'

    res_list=[]
    carrot.insert(0,['x' for i in range(len(carrot[0])+2)])
    carrot.append(['x' for i in range(len(carrot[1])+2)])
    for num in range(1,len(carrot)-1):
        carrot[num].insert(0,'x')
        carrot[num].append('x')
    start_point=((len(carrot)//2-1 if len(carrot)%2==0 else len(carrot)//2),(len(carrot[0])//2-1 if len(carrot[0])%2==0 else len(carrot[0])//2))
    i = start_point[0]
    j = start_point[1]
    add_remove(i, j)
    while carrot[i-1][j]!='x' or carrot[i][j-1]!='x' or carrot[i+1][j]!='x' or carrot[i][j+1]!='x':
        list1=[((i-1),j),(i,(j-1)),((i+1),j),(i,(j+1))]
        max_value=max([carrot[k[0]][k[1]] for k in list1 if carrot[k[0]][k[1]]!='x'])
        next_point=[list1[index] for index,value in enumerate(list1) if carrot[value[0]][value[1]]==max_value]
        i=next_point[0][0]
        j=next_point[0][1]
        add_remove(i,j)
    return sum(res_list)

carrot = [[5, 7, 6, 3],
          [2, 4, 8, 12],
          [3, 5, 10, 7],
          [4, 16, 4, 17]]
assert solution(carrot) == 83
carrot = [[5, 3, 7, 1, 7],
          [4, 6, 5, 2, 8],
          [2, 1, 1, 4, 6]]
assert solution(carrot) == 30