Question

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

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

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]);
  }
}

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]);
  }
};

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
}