Minimum Moves for a Squirrel to Carry Every Nut to a Tree One at a Time

A squirrel and a tree are on a rectangular grid with height rows and width columns, and several nuts lie on other cells of the grid. The squirrel must carry every nut to the tree. It can hold at most one nut at a time, and each move takes it to a cell that shares a side with its current cell.

Return the minimum total number of moves the squirrel needs to deliver all the nuts to the tree.

Function Signature

def min_collection_moves(height: int, width: int, tree: list[int], squirrel: list[int], nuts: list[list[int]]) -> int:

tree, squirrel and every nuts[i] are cells given as [row, col].

Rules

• Row 0 is the top row and column 0 is the leftmost column. One move takes the squirrel from (row, col) to (row - 1, col), (row + 1, col), (row, col - 1) or (row, col + 1). It never leaves the grid, and the grid has no obstacles.
• The squirrel starts without a nut. Picking up a nut on its current cell and dropping a nut at the tree cost no moves.
• The squirrel may walk over cells that hold other nuts without picking them up, and it never holds two nuts at once.
• The nuts may be delivered in any order. Counting stops when the last nut is dropped at the tree; the squirrel does not need to go anywhere afterwards.
• Return the minimum total number of moves over all delivery orders.

Constraints

• 1 <= height <= 100 and 1 <= width <= 100
• 0 <= row < height and 0 <= col < width for the tree, the squirrel and every nut.
• 1 <= len(nuts) <= 5000
• The nuts lie on distinct cells, and no nut lies on the tree's cell.
• The squirrel may start on the tree's cell or on a cell that holds a nut.
• The answer is less than 2 * 10^6.

Examples

Example 1

Input: height = 4, width = 5, tree = [1, 1], squirrel = [3, 4], nuts = [[0, 4], [3, 1]]
Output: 11

Fetching the nut at (0, 4) first takes 3 moves to reach it and 4 moves to carry it to the tree. The nut at (3, 1) then takes 2 moves out and 2 back, for 11 in total. Fetching (3, 1) first costs 3 + 2 + 4 + 4 = 13.

Example 2

Input: height = 1, width = 10, tree = [0, 2], squirrel = [0, 9], nuts = [[0, 0], [0, 4]]
Output: 11

Fetching (0, 4) first costs 5 + 2, and (0, 0) then costs 2 + 2, for 11. Fetching (0, 0) first costs 9 + 2 + 2 + 2 = 15.

Example 3

Input: height = 3, width = 3, tree = [1, 1], squirrel = [0, 0], nuts = [[0, 0], [2, 2], [0, 2]]
Output: 10

The squirrel picks up the nut on its own cell and carries it 2 moves to the tree. Each of the other two nuts takes 2 moves out and 2 back, for 2 + 4 + 4 = 10.