|
1 | 1 | package com.fishercoder.solutions;
|
2 | 2 |
|
3 |
| -/** |
4 |
| - * 573. Squirrel Simulation |
5 |
| - * |
6 |
| - * There's a tree, a squirrel, and several nuts. |
7 |
| - * Positions are represented by the cells in a 2D grid. |
8 |
| - * Your goal is to find the minimal distance for the squirrel to collect all the nuts and |
9 |
| - * put them under the tree one by one. |
10 |
| - * The squirrel can only take at most one nut at one time and can move in four directions - |
11 |
| - * up, down, left and right, to the adjacent cell. |
12 |
| - * The distance is represented by the number of moves. |
13 |
| -
|
14 |
| - Example 1: |
15 |
| -
|
16 |
| - Input: |
17 |
| - Height : 5 |
18 |
| - Width : 7 |
19 |
| - Tree position : [2,2] |
20 |
| - Squirrel : [4,4] |
21 |
| - Nuts : [[3,0], [2,5]] |
22 |
| - Output: 12 |
23 |
| -
|
24 |
| - Explanation: |
25 |
| -
|
26 |
| - Note: |
27 |
| -
|
28 |
| - All given positions won't overlap. |
29 |
| - The squirrel can take at most one nut at one time. |
30 |
| - The given positions of nuts have no order. |
31 |
| - Height and width are positive integers. 3 <= height * width <= 10,000. |
32 |
| - The given positions contain at least one nut, only one tree and one squirrel. |
33 |
| - */ |
34 | 3 | public class _573 {
|
35 | 4 |
|
36 | 5 | public static class Solution1 {
|
37 | 6 |
|
38 | 7 | /**
|
39 | 8 | * reference: https://leetcode.com/articles/squirrel-simulation
|
40 |
| - * |
| 9 | + * <p> |
41 | 10 | * 1. The order in which to pick the nuts does not matter except the first one
|
42 | 11 | * because for all the other nuts, the squirrel needs to travel back and forth.
|
43 |
| - * |
| 12 | + * <p> |
44 | 13 | * 2. For the first nut to be picked, there's some distance we might be able to save, what is this distance?
|
45 | 14 | * It is the difference between the squirrel's original starting point to the first nut and that the distance from this
|
46 | 15 | * first nut to the tree.
|
47 | 16 | * This is because, only for the first nut, the squirrel does NOT need to travel back and forth, it only needs to travel from
|
48 | 17 | * its starting position to the nut position and then return to the tree.
|
49 |
| - * |
| 18 | + * <p> |
50 | 19 | * 3. For the rest of all other nuts, the squirrel always needs to go back and forth.
|
51 |
| - * |
| 20 | + * <p> |
52 | 21 | * 4. So how can we find the first nut to go to so that we could have the maximum saved distance?
|
53 | 22 | * We iterate through all of the nuts and keep updating the savedDist as below:
|
54 | 23 | */
|
|
0 commit comments