0573：松鼠模拟（★）

力扣第 573 题

题目

现在有一棵树，一只松鼠和一些坚果。位置由二维网格的单元格表示。你的目标是找到松鼠收集所有坚果的最小路程，且坚果是一颗接一颗地被放在树下。松鼠一次最多只能携带一颗坚果，松鼠可以向上，向下，向左和向右四个方向移动到相邻的单元格。移动次数表示路程。

输入 1:

输入:
高度 : 5
宽度 : 7
树的位置 : [2,2]
松鼠 : [4,4]
坚果 : [[3,0], [2,5]]
输出: 12
解释:
​​​​​

注意:

1. 所有给定的位置不会重叠。
2. 松鼠一次最多只能携带一颗坚果。
3. 给定的坚果位置没有顺序。
4. 高度和宽度是正整数。 3 <= 高度 * 宽度 <= 10,000。
5. 给定的网格至少包含一颗坚果，唯一的一棵树和一只松鼠。

分析

先假设松鼠一开始在就在树的位置，最小路程就是曼哈顿距离之和。

然后要将第一步树到某坚果的路程替换为松鼠到某坚果的路程，找替换代价最小的即可。

解答

1
2
3
4
5

def minDistance(self, height: int, width: int, tree: List[int], squirrel: List[int], nuts: List[List[int]]) -> int:
	def cal(p1, p2):
		return abs(p1[0]-p2[0])+abs(p1[1]-p2[1])
	res = 2*sum(cal(tree, p) for p in nuts)
	return res + min(cal(squirrel, p)-cal(tree, p) for p in nuts)

48 ms