Leetcode 573 - Squirrel Simulation

http://bookshadow.com/weblog/2017/05/07/leetcode-squirrel-simulation/

There's a tree, a squirrel, and several nuts. Positions are represented by the cells in a 2D grid. Your goal is to find the minimal distance for the squirrel to collect all the nuts and put them under the tree one by one. 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. The distance is represented by the number of moves.

Example 1:

Input: 
Height : 5
Width : 7
Tree position : [2,2]
Squirrel : [4,4]
Nuts : [[3,0], [2,5]]
Output: 12
Explanation:

Note:

1. All given positions won't overlap.
2. The squirrel can take at most one nut at one time.
3. The given positions of nuts have no order.
4. Height and width are positive integers. 3 <= height * width <= 10,000.
5. The given positions contain at least one nut, only one tree and one squirrel.

解题思路：

求所有坚果到树的曼哈顿距离之和的2倍，记为total

求松鼠到坚果的曼哈顿距离 - 树到坚果曼哈顿距离的最小值， 该值与total之和即为最终答案

https://blog.csdn.net/magicbean2/article/details/78899934
松鼠的行为可以分为两个步骤：1）走到某个坚果i那里，然后把坚果i移动到树下；2）依次走到其它坚果那里，带上坚果之后返回来。所以松鼠的最短行程只取决于第一次选择哪个坚果，这是因为选择坚果i之后，松鼠需要额外走从它当前位置到坚果i的距离，但是却可以省下从树到坚果i之间的距离，所以我们的目标就是找到i，使得distance(squireel, nuts[i]) - distance(tree, nuts[i])最小。确定i之后，再按照松鼠的移动轨迹计算路程即可。

    int minDistance(int height, int width, vector<int>& tree, vector<int>& squirrel, vector<vector<int>>& nuts) {
        int min_dist = INT_MAX, min_index = -1, ret = 0, dist;
        for (int i = 0; i < nuts.size(); ++i) {
            dist = distance(squirrel, nuts[i]) - distance(nuts[i], tree);
            if (dist < min_dist) {
                min_dist = dist;
                min_index = i;
            }
        }
        ret += min_dist;
        for (int i = 0; i < nuts.size(); ++i) {
            ret += 2 * distance(nuts[i], tree);
        }
        return ret;
    }
private:
    int distance(vector<int> &from, vector<int> &to) {
        return abs(from[0] - to[0]) + abs(from[1] - to[1]);
    }

http://www.cnblogs.com/grandyang/p/6919923.html
本题说有一只小松鼠，一堆在不同位置的粟子，还有一棵树，小松鼠目标是把所有的粟子都运到树的位置，问怎样的顺序可以使用最少的步数。那么我们这么想，如果小松鼠本身就在树的位置，那么把所有的栗子运回树的步数就是一个定值，为每个粟子距树的距离总和乘以2。那么只有当小松鼠不在树的位置时候，它首先要走到一个粟子的位置，然后再去树那儿。而且一旦小松鼠到了树那，再出发，之后的步数就是定值了。所以关键就在于决定小松鼠首先去哪个粟子那。博主最开始犯了一个这道题很容易犯的一个错误，就是在选起始粟子的时候的判定条件是松鼠到该粟子的距离加上该粟子到树的距离之和最小当作判定条件，其实这样是不对的。举个简单的反例，比如此时有两个粟子A和B，小松鼠到粟子A的距离为2，粟子A到树的距离为1，小松鼠到粟子B的距离为2，粟子B到树的距离为2。那么按照博主之前的选择方法，会选先去粟子A，因为小松鼠到粟子A再到树的距离之和为3，小于先去粟子B再去树的距离之和(为4)。然而小松鼠先去粟子A的话，总距离就是7，而如果先去粟子B的话，总距离为6，这就说明之前的判定条件不对。那么正确思路应该是，假设小松树最先应该去粟子i，那么我们假设粟子i到树的距离为x，小松鼠到粟子i的距离为y，那么如果小松鼠不去粟子i，累加步数就是2x，如果小松鼠去粟子i，累加步数就是x+y，我们希望x+y尽可能的小于2x，那么就是y尽可能小于x，即x-y越大越好。这样我们遍历每个粟子，找出x-y最大的那个，让小松鼠先去捡就好了

https://discuss.leetcode.com/topic/88490/java-5-liner-o-nuts-time-o-1-space

Proof: Let the minimum distance from each nut to the tree be a_1, ..., a_n and let the minimum distance from each nut to the initial squirrel position be b_1, ..., b_n. Note that the minimum distance between two positions in the matrix is determined by their Manhattan distance.

Then, if the squirrel were to start at the tree, then the minimum total distance required to collect all the nuts is 2a_1 + ... + 2a_n. However, since the squirrel starts elsewhere, we just need to substitute one of the 2a_i terms with a_i + b_i. Or equivalently, we replace one of the a_i terms in the sum with b_i. To minimize the total sum value at the end, we choose i that maximizes a_i - b_i.

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 dist = Math.abs(tree[0] - nut[0]) + Math.abs(tree[1] - nut[1]);
        sum += 2*dist;
        maxDiff = Math.max(maxDiff, dist - Math.abs(squirrel[0] - nut[0]) - Math.abs(squirrel[1] - nut[1]));
    }
    return sum - maxDiff;
}

https://discuss.leetcode.com/topic/88512/java-solution-o-n-manhattan-distance

    public int minDistance(int height, int width, int[] tree, int[] squirrel, int[][] nuts) {
        int n = nuts.length;
        int[] nutToTree = new int[n];
        int[] nutToSquirrel = new int[n];
        
        int sum = 0;
        for (int i = 0; i < n; i++) {
            nutToTree[i] = Math.abs(nuts[i][0] - tree[0]) + Math.abs(nuts[i][1] - tree[1]);
            sum += nutToTree[i] * 2;
            nutToSquirrel[i] = Math.abs(nuts[i][0] - squirrel[0]) + Math.abs(nuts[i][1] - squirrel[1]);
        }
        
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int dist = sum + nutToSquirrel[i] - nutToTree[i];
            min = Math.min(min, dist);
        }
        
        return min;
    }

https://discuss.leetcode.com/topic/88511/easy-to-understand-concise-o-n-solution-with-explanation

Since squirel needs to travel to the tree every time after picking a nut, it needs to travel to the first nut, get it to the tree and then visit other nuts one by one. So total distance would be
dist(squirrel,first_nut) + dist(fist_nut, tree) + 2 * sum(dist(nut,tree)) - 2 * dist(fist_nut, tree) = dist(squirrel,first_nut) - dist(fist_nut, tree) + 2 * sum(dist(nut,tree))
2 * sum(dist(nut,tree)) is constant, so we just need to minimize dist(squirrel,first_nut) - dist(fist_nut, tree) to select the first nut.