You are given two integers height and width representing a garden of size height x width. You are also given:
tree where tree = [treer, treec] is the position of the tree in the garden,squirrel where squirrel = [squirrelr, squirrelc] is the position of the squirrel in the garden,nuts where nuts[i] = [nutir, nutic] is the position of the ith nut in the garden.The squirrel can only take at most one nut at one time and can move in four directions: up, down, left, and right, to the adjacent cell.
Return the minimal distance for the squirrel to collect all the nuts and put them under the tree one by one.
The distance is the number of moves.
Example 1:
Input: height = 5, width = 7, tree = [2,2], squirrel = [4,4], nuts = [[3,0], [2,5]] Output: 12 Explanation: The squirrel should go to the nut at [2, 5] first to achieve a minimal distance.
Example 2:
Input: height = 1, width = 3, tree = [0,1], squirrel = [0,0], nuts = [[0,2]] Output: 3
Constraints:
1 <= height, width <= 100tree.length == 2squirrel.length == 21 <= nuts.length <= 5000nuts[i].length == 20 <= treer, squirrelr, nutir <= height0 <= treec, squirrelc, nutic <= widthObserving the squirrel's movement path, we can see that the squirrel will first move to the position of a nut, then move to the position of the tree. After that, the total movement path of the squirrel is equal to "the sum of the distances from the remaining nuts to the tree" multiplied by $2$.
Therefore, we only need to select a nut as the squirrel's first target, such that the sum of its distance to the tree is minimized, to obtain the shortest path.
The time complexity is $O(n)$, where $n$ is the number of nuts. The space complexity is $O(1)$.
Java
C++
Go
TypeScript
Rust
C#
Don't Make This Coding Interview Mistake! | Jewels and Stones - Leetcode 771 • Greg Hogg • 443,129 views views
Watch 9 more video solutions →Practice Squirrel Simulation with our built-in code editor and test cases.
Practice on FleetCode