给定一个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
joyoko
(徐子宇)
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
dperfly
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
}
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
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
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