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 ```python 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** ```text 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** ```text 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** ```text 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.