> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0573-squirrel-simulation.md).

# 0573. Squirrel Simulation

<https://leetcode.com/problems/squirrel-simulation>

## Description

You are given two integers `height` and `width` representing a garden of size `height x width`. You are also given:

* an array `tree` where `tree = [treer, treec]` is the position of the tree in the garden,
* an array `squirrel` where `squirrel = [squirrelr, squirrelc]` is the position of the squirrel in the garden,
* and an array `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:**

![](https://assets.leetcode.com/uploads/2021/04/24/squirrel1-grid.jpg)

```
**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:**

![](https://assets.leetcode.com/uploads/2021/04/24/squirrel2-grid.jpg)

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

**Constraints:**

* `1 <= height, width <= 100`
* `tree.length == 2`
* `squirrel.length == 2`
* `1 <= nuts.length <= 5000`
* `nuts[i].length == 2`
* `0 <= treer, squirrelr, nutir <= height`
* `0 <= treec, squirrelc, nutic <= width`

## ac

```java
class Solution {
    public int minDistance(int height, int width, int[] tree, int[] squirrel, int[][] nuts) {
        int sum = 0, maxDiff = Integer.MIN_VALUE;
        for (int[] nut : nuts) {
            int t = dist(nut, tree);
            int s = dist(nut, squirrel);
            sum += 2*t;
            maxDiff = Math.max(maxDiff, t - s);
        }

        return sum - maxDiff;
    }

    public int dist(int[] num1, int[] num2) {
        return Math.abs(num1[0] - num2[0]) + Math.abs(num1[1] - num2[1]);
    }
}

/*
1) nuts to tree: 2*t1 + 2*t2 +...+ 2*ti; 2) one nut is different, it only move once, say tj. and need to add distance(squirrel, nut), so it's sum - tj + sj -> sum - (tj - sj); 3) for every nut, calculate distance to tree and squirrel
*/
```