573. Squirrel Simulation

这是leetcode weekly contest31的第三题。

松鼠模拟。松鼠收集所有松果到松树底下，每次只能拿一个松果。这题想通了就是一道送分题，没想通就是做不出。我一开始想的是，也许应该用DFS遍历所有拿松果的顺序。wack说用O(N)就行。看了答案之后才发现原来只有第一次去拿松果是特殊情况。如果把松树的原点设在松树底下，那不管怎么拿松果，要走的Distance都是一样的。所以minDistance就在于第一次松鼠先去拿哪一个松果。

代码：

    public int minDistance(int height, int width, int[] tree, int[] squirrel, int[][] nuts) {
        int sum = 0;
        int extra = Integer.MAX_VALUE;
        for (int i = 0; i < nuts.length; i++) {
            int nut2tree = dist(nuts[i], tree);
            int nut2squirrel = dist(nuts[i], squirrel);
            sum += nut2tree ;
            extra = Math.min(extra, nut2squirrel - nut2tree);
        }
        return sum * 2 + extra;
    }


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