[C++] Clean Code with Explanation

  • 3
     * find out the minimum distance dist[i] to all nuts, and the dist_sum;
     * if Squirrel is start at the tree, then the min distance to collect all nuts would be 2 * dist_sum;
     * but most likely, it is not at the tree, Squirrel need to go to a nuts, then come to the tree single-trip, the round trip to the rest nuts.
     * The sum would be : dist_sum + (dist_Squirrel_to_nut[I] - dist_nut[I]-to-tree), and we want the latter to be minimal.
    class Solution {
        int minDistance(int height, int width, vector<int>& tree, vector<int>& squirrel, vector<vector<int>>& nuts) {
            int sum = 0;
            int minextra = INT_MAX; // nut with the minimal (nut2squirrel - nut2tree)
            for (vector<int> nut : nuts) {
                int nut2tree = dist(nut, tree);
                int nut2squirrel = dist(nut, squirrel);
                sum += nut2tree;
                minextra = min(minextra, nut2squirrel - nut2tree);
            return 2 * sum + minextra;
        int dist(vector<int> a, vector<int> b) {
            return abs(a[0] - b[0]) + abs(a[1] - b[1]);

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.