package com.fishercoder.solutions;

/**
 * 573. 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:

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

    /**reference: https://leetcode.com/articles/squirrel-simulation
     *
     * 1. The order in which to pick the nuts does not matter except the first one
     * because for all the other nuts, the squirrel needs to travel back and forth.
     *
     * 2. For the first nut to be picked, there's some distance we might be able to save, what is this distance?
     * It is the difference between the squirrel's original starting point to the first nut and that the distance from this
     * first nut to the tree.
     * This is because, only for the first nut, the squirrel does NOT need to travel back and forth, it only needs to travel from
     * its starting position to the nut position and then return to the tree.
     *
     * 3. For the rest of all other nuts, the squirrel always needs to go back and forth.
     *
     * 4. So how can we find the first nut to go to so that we could have the maximum saved distance?
     * We iterate through all of the nuts and keep updating the savedDist as below:
     * */
    public int minDistance(int height, int width, int[] tree, int[] squirrel, int[][] nuts) {
        int totalDist = 0;
        int savedDist = Integer.MIN_VALUE;
        for (int[] nut : nuts) {
            totalDist += (getDist(nut, tree) * 2);//it needs to travel back and forth, so times two
            savedDist = Math.max(savedDist, getDist(nut, tree) - getDist(nut, squirrel));
        }
        return totalDist - savedDist;
    }

    private int getDist(int[] pointA, int[] pointB) {
        return Math.abs(pointA[0] - pointB[0]) + Math.abs(pointA[1] - pointB[1]);
    }
}

@@ -953,19 +953,72 @@
  %7B%0A%0A    
-/**
+public static class Solution1 %7B%0A%0A        /**%0A         * 
 referenc
@@ -1071,26 +1071,34 @@
 lation%0A     
-*%0A
+    *%0A    
      * 1. Th
@@ -1173,16 +1173,20 @@
 ne%0A     
+  
+  
 * becaus
@@ -1257,26 +1257,34 @@
 forth.%0A     
-*%0A
+    *%0A    
      * 2. Fo
@@ -1389,16 +1389,20 @@
 e?%0A     
+ 
+   
 * It is 
@@ -1517,16 +1517,20 @@
 is%0A     
+    
 * first 
@@ -1551,16 +1551,20 @@
 e.%0A     
+   
+ 
 * This i
@@ -1685,16 +1685,20 @@
 om%0A     
+    
 * its st
@@ -1767,23 +1767,31 @@
 e.%0A     
-*%0A
+    *%0A  
      
+  
 * 3. For
@@ -1868,26 +1868,34 @@
 forth.%0A     
-*%0A
+    *%0A    
      * 4. So
@@ -1989,16 +1989,20 @@
 e?%0A     
+    
 * We ite
@@ -2081,17 +2081,19 @@
     
-*
+   
  */%0A    
 publ
@@ -2084,24 +2084,28 @@
      */%0A    
+   
+ 
 public int m
@@ -2186,24 +2186,28 @@
 ) %7B%0A        
+    
 int totalDis
@@ -2213,16 +2213,20 @@
 st = 0;%0A
+    
         
@@ -2268,16 +2268,20 @@
         
+ 
+   
 for (int
@@ -2289,32 +2289,36 @@
 %5D nut : nuts) %7B%0A
+    
             tota
@@ -2401,16 +2401,20 @@
 mes two%0A
+    
         
@@ -2503,18 +2503,26 @@
         
-%7D%0A
+    %7D%0A    
         
@@ -2559,11 +2559,19 @@
     
+  
+  
 %7D%0A%0A
+    
     
@@ -2616,24 +2616,28 @@
 %5D pointB) %7B%0A
+    
         retu
@@ -2706,16 +2706,26 @@
 tB%5B1%5D);%0A
+        %7D%0A
     %7D%0A%7D%0A

refactor 573