【Leetcode】573. Squirrel Simulation

题目地址：

https://leetcode.com/problems/squirrel-simulation/description/

给定一个二维矩阵，里面有若干个果子，一个松鼠和一棵树，松鼠每一步可以走四个方向，它每次可以最多携带一个果子，并且它要将每个果子都搜集到树的位置。问至少要走多少步。

设松鼠位置是$s$，果子的位置是$n_i$，树的位置是$t$，则除了第一个果子以外，别的果子都需要来回在树和果子之间走两次，所以总距离为$2{\sum }_i|n_{i}t|-|n_{0}t|+|n_{0}s|$，$n_0$为某个第一个采集的果子。要最小化这个其实就是要最大化$|n_{0}t|-|n_{0}s|$，直接暴力枚举$n_0$即可。代码如下：

class Solution {
 public:
  int minDistance(int height, int width, vector<int>& tree,
                  vector<int>& squirrel, vector<vector<int>>& nuts) {
    int res = 0, d = INT_MIN;
    auto dist = [&](vector<int>& a, vector<int>& b) {
      return abs(a[0] - b[0]) + abs(a[1] - b[1]);
    };

    for (auto nut : nuts) {
      res += dist(nut, tree) * 2;
      d = max(d, dist(nut, tree) - dist(nut, squirrel));
    }

    return res - d;
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

时间复杂度$O(n)$，$n$是果子数量，空间$O(1)$。