# Cut Off Trees for Golf Event

`Graph`, `Breadth-first Search`, `Shortest Path`

**Hard**

You are asked to cut off trees in a forest for a golf event. The forest is represented as a non-negative 2D map, in this map:

1. `0` represents the `obstacle` can't be reached.
2. `1` represents the `ground` can be walked through.
3. `The place with number bigger than 1` represents a `tree` can be walked through, and this positive number represents the tree's height.

You are asked to cut off **all** the trees in this forest in the order of tree's height - always cut off the tree with lowest height first. And after cutting, the original place has the tree will become a grass (value 1).

You will start from the point (0, 0) and you should output the minimum steps **you need to walk** to cut off all the trees. If you can't cut off all the trees, output -1 in that situation.

You are guaranteed that no two`trees`have the same height and there is at least one tree needs to be cut off.

**Example 1:**

```
Input:

[
 [1,2,3],
 [0,0,4],
 [7,6,5]
]

Output:
 6
```

**Example 2:**

```
Input:

[
 [1,2,3],
 [0,0,0],
 [7,6,5]
]

Output:
 -1
```

**Example 3:**

```
Input:

[
 [2,3,4],
 [0,0,5],
 [8,7,6]
]

Output:
 6

Explanation:
 You started from the point (0,0) and you can cut off the tree in (0,0) directly without walking.
```

**Hint**: size of the given matrix will not exceed 50x50.

## Solution & Analysis

跟The Maze系列有些类似；都是寻找最短路径，但是这里要计算每次从新起点到下一棵要砍的树的最短距离，所以shortest distance需要被call多次（每次砍树都要先call）。

### 基本框架：

* 先找到所有的树，按照高度从低到高排序
* 从(0,0)作为起点，每次都寻找到下一棵树的最短路径长度，并更新总步数长度；以及更新起点位置和下一个目标位置
* 如果最短路径不存在，返回-1。

最短路径的寻找方式有许多种，在grid类型的graph中，有十分简便的实现：

因为grid类型的graph可以看成edge的weight/length均为1的无向图，因此BFS可以一层一层地遍历，到达目标点的总步长也就是遍历的层数，每一层开始前记录当前层中节点数量，遍历完之后，再遍历下一层，放在queue中的是每一层的节点。如果找到目标位置，则返回当前的层数即可。

### BFS

```java
class Solution {
    public int cutOffTree(List<List<Integer>> forest) {
        // Get all the trees with h-height, r-row, c-column and sort by height
        List<int[]> trees = new ArrayList<>();
        int[][] map = new int[forest.size()][forest.get(0).size()];
        for (int r = 0; r < forest.size(); r++) {
            for (int c = 0; c < forest.get(r).size(); c++) {
                int h = forest.get(r).get(c);
                map[r][c] = h;
                if (h > 1) {
                    trees.add(new int[] {h, r, c});
                }
            }
        }

        // Sort trees based on height of trees
        Collections.sort(trees, (t1, t2) -> Integer.compare(t1[0], t2[0]));

        int ans = 0;
        int r0 = 0;
        int c0 = 0;
        // Find distance from current position to next tree
        for (int[] tree: trees) {
            int d = dist(map, r0, c0, tree[1], tree[2]);
            if (d < 0) {
                return -1;
            }
            ans += d;
            r0 = tree[1];
            c0 = tree[2];
        }
        return ans;
    }

    private static int[][] dirs = {{-1, 0}, {1, 0} , {0, -1}, {0, 1}};

    private int dist(int[][] map, int sr, int sc, int tr, int tc) {
        int distance = 0;
        boolean[][] visited = new boolean[map.length][map[0].length];
        Queue<int[]> q = new LinkedList<int[]>();
        q.offer(new int[] {sr, sc});
        visited[sr][sc] = true;

        while (!q.isEmpty()) {
            int levelSize = q.size();
            while (levelSize-- > 0) {
                int[] pos = q.poll();

                if (pos[0] == tr && pos[1] == tc) {
                    return distance;
                }

                for (int[] dir: dirs) {
                    int nr = pos[0] + dir[0];
                    int nc = pos[1] + dir[1];
                    if (nr >= 0 && nr < map.length && nc >= 0 && nc < map[0].length) {
                        if (map[nr][nc] != 0 && !visited[nr][nc]) {
                            q.offer(new int[] {nr, nc});
                            visited[nr][nc] = true;
                        }
                    }
                }
            }
            distance++;
        }
        return -1;
    }
}
```

### Another BFS (Store distance in int\[] {r, c, dist})

类似上面的一层一层BFS，这里就是把距离放到每个节点的int\[]中.

Runtime: 258 ms, faster than 84.21% of Java online submissions for Cut Off Trees for Golf Event.

Memory Usage: 46.7 MB, less than 100.00% of Java online submissions for Cut Off Trees for Golf Event.

```java
class Solution {
    public int cutOffTree(List<List<Integer>> forest) {
        // Get all the trees with h-height, r-row, c-column and sort by height
        List<int[]> trees = new ArrayList<>();
        int[][] map = new int[forest.size()][forest.get(0).size()];
        for (int r = 0; r < forest.size(); r++) {
            for (int c = 0; c < forest.get(r).size(); c++) {
                int h = forest.get(r).get(c);
                map[r][c] = h;
                if (h > 1) {
                    trees.add(new int[] {h, r, c});
                }
            }
        }

        // Sort trees based on height of trees
        Collections.sort(trees, (t1, t2) -> Integer.compare(t1[0], t2[0]));

        int ans = 0;
        int r0 = 0;
        int c0 = 0;
        // Find distance from current position to next tree
        for (int[] tree: trees) {
            int d = dist(forest, r0, c0, tree[1], tree[2]);
            if (d < 0) {
                return -1;
            }
            ans += d;
            r0 = tree[1];
            c0 = tree[2];
        }
        return ans;
    }

    private static int[][] dirs = {{-1, 0}, {1, 0} , {0, -1}, {0, 1}};

    public int dist(List<List<Integer>> forest, int sr, int sc, int tr, int tc) {
        int R = forest.size(), C = forest.get(0).size();
        Queue<int[]> queue = new LinkedList();
        boolean[][] seen = new boolean[R][C];

        queue.add(new int[]{sr, sc, 0});
        seen[sr][sc] = true;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            if (cur[0] == tr && cur[1] == tc) {
                return cur[2];
            }
            for (int[] dir: dirs) {
                int r = cur[0] + dir[0];
                int c = cur[1] + dir[1];
                if (0 <= r && r < R && 0 <= c && c < C &&
                    !seen[r][c] && forest.get(r).get(c) > 0) {
                    seen[r][c] = true;
                    queue.add(new int[]{r, c, cur[2] + 1});
                }
            }
        }
        return -1;
    }
}
```

### Dijkstra's Algorithm (Greedy + PriorityQueue based)

与**BFS**的**区别**就在于不再是一层一层遍历，而是每次通过在**PriorityQueue**中`poll()`，得到当前待遍历的节点中到起始点距离最短的节点，然后四方向寻找，如果发现距离比`distance[][]` matrix所记录的要小，就更新`distance[][]`matrix，并且将该节点以及其到起始点的距离放入**PriorityQueue**中，进行下一轮`poll()`的过程。

**Performance**:

* **Runtime**: **911 ms, faster than 3.64%** of Java online submissions for Cut Off Trees for Golf Event.&#x20;
* **Memory** **Usage**: **46.7 MB, less than 100.00%** of Java online submissions for Cut Off Trees for Golf Event.

```java
class Solution {
    public int cutOffTree(List<List<Integer>> forest) {
        // Get all the trees with h-height, r-row, c-column and sort by height
        List<int[]> trees = new ArrayList<>();
        int[][] map = new int[forest.size()][forest.get(0).size()];
        for (int r = 0; r < forest.size(); r++) {
            for (int c = 0; c < forest.get(r).size(); c++) {
                int h = forest.get(r).get(c);
                map[r][c] = h;
                if (h > 1) {
                    trees.add(new int[] {h, r, c});
                }
            }
        }

        // Sort trees based on height of trees
        Collections.sort(trees, (t1, t2) -> Integer.compare(t1[0], t2[0]));

        int ans = 0;
        int r0 = 0;
        int c0 = 0;
        // Find distance from current position to next tree
        for (int[] tree: trees) {
            int d = dist(map, r0, c0, tree[1], tree[2]);
            if (d < 0) {
                return -1;
            }
            ans += d;
            r0 = tree[1];
            c0 = tree[2];
        }
        return ans;
    }

    private static int[][] dirs = {{-1, 0}, {1, 0} , {0, -1}, {0, 1}};

    // Dijkstra's Algorithm to Find Shortest Distance
    private int dist(int[][] map, int sr, int sc, int tr, int tc) {

        // Init distance matrix
        int[][] distance = new int[map.length][map[0].length];
        for (int[] row: distance) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        distance[sr][sc] = 0;

        // Init priority queue for vertices to traverse
        PriorityQueue<int[]> q = new PriorityQueue<int[]>((a, b) -> a[2] - b[2]);
        q.offer(new int[] {sr, sc, 0});

        while (!q.isEmpty()) {
            int[] pos = q.poll();

            for (int[] dir: dirs) {
                int nr = pos[0] + dir[0];
                int nc = pos[1] + dir[1];
                if (nr >= 0 && nr < map.length && nc >= 0 && nc < map[0].length) {
                    // Update distance matrix and add the vertex to priority queue
                    if (map[nr][nc] != 0 && (pos[2] + 1 < distance[nr][nc])) {
                        distance[nr][nc] = pos[2] + 1;
                        q.offer(new int[] {nr, nc, pos[2] + 1});
                    }
                }
            }
        }

        if (distance[tr][tc] == Integer.MAX_VALUE) {
            return -1;
        }
        return distance[tr][tc];
    }
}
```

### Approach: A\* Search <a href="#approach-2-a-search-accepted" id="approach-2-a-search-accepted"></a>

TODO: <https://leetcode.com/articles/cutoff-trees-for-golf-event/?orderBy=most_votes>

### Approach: Hadlock's Algorithm

TODO: <https://leetcode.com/articles/cutoff-trees-for-golf-event/?orderBy=most_votes>

## Reference

<http://www.cnblogs.com/grandyang/p/8379506.html>