You are given two integers height and width representing a grid of size height $ imes$ width. You are also given an integer array tree of length $2$ representing the coordinates of a tree, an integer array squirrel of length $2$ representing the starting coordinates of a squirrel, and an array of integer arrays nuts where each nuts[i] represents the coordinates of a nut.

The squirrel can carry at most $1$ nut at a time and travels across the grid where moving $1$ cell horizontally or vertically costs $1$ unit of distance. The distance between any two positions $(r_1, c_1)$ and $(r_2, c_2)$ is given by the Manhattan distance $|r_1 - r_2| + |c_1 - c_2|$.

Return the minimum total distance the squirrel must travel to collect all the nuts and bring them to the tree one by one.

Constraints:

• $1 \leq$ height, width $\leq 100$

• tree.length $= 2$

• squirrel.length $= 2$

• $1 \leq$ nuts.length $\leq 5000$

• nuts[i].length $= 2$

• $0 \leq$ tree_r, squirrel_r, nut_{ir} $\leq$ height

• $0 \leq$ tree_c, squirrel_c, nut_{ic} $\leq$ width

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.