573. 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:

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 <= 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

Solutions

Solution 1

Python Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def minDistance(
        self,
        height: int,
        width: int,
        tree: List[int],
        squirrel: List[int],
        nuts: List[List[int]],
    ) -> int:
        x, y, a, b = *tree, *squirrel
        s = sum(abs(i - x) + abs(j - y) for i, j in nuts) * 2
        ans = inf
        for i, j in nuts:
            c = abs(i - x) + abs(j - y)
            d = abs(i - a) + abs(j - b) + c
            ans = min(ans, s + d - c * 2)
        return ans

Java Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int minDistance(int height, int width, int[] tree, int[] squirrel, int[][] nuts) {
        int ans = Integer.MAX_VALUE;
        int s = 0;
        for (int[] a : nuts) {
            s += f(a, tree);
        }
        s *= 2;
        for (int[] a : nuts) {
            int c = f(a, tree);
            int d = f(a, squirrel) + c;
            ans = Math.min(ans, s + d - c * 2);
        }
        return ans;
    }

    private int f(int[] a, int[] b) {
        return Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]);
    }
}

C++ Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int minDistance(int height, int width, vector<int>& tree, vector<int>& squirrel, vector<vector<int>>& nuts) {
        int ans = INT_MAX;
        int s = 0;
        for (auto& a : nuts) {
            s += f(a, tree);
        }
        s *= 2;
        for (auto& a : nuts) {
            int c = f(a, tree);
            int d = f(a, squirrel) + c;
            ans = min(ans, s + d - c * 2);
        }
        return ans;
    }

    int f(vector<int>& a, vector<int>& b) {
        return abs(a[0] - b[0]) + abs(a[1] - b[1]);
    }
};

Go Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func minDistance(height int, width int, tree []int, squirrel []int, nuts [][]int) int {
	f := func(a, b []int) int {
		return abs(a[0]-b[0]) + abs(a[1]-b[1])
	}
	ans := math.MaxInt32
	s := 0
	for _, a := range nuts {
		s += f(a, tree)
	}
	s *= 2
	for _, a := range nuts {
		c := f(a, tree)
		d := f(a, squirrel) + c
		ans = min(ans, s+d-c*2)
	}
	return ans
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}