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