LeetCode 675 - Cut Off Trees for Golf Event

https://www.cnblogs.com/grandyang/p/8379506.html

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.

https://leetcode.com/problems/cut-off-trees-for-golf-event/discuss/107404/Java-solution-PriorityQueue-%2B-BFS

1. Since we have to cut trees in order of their height, we first put trees (int[] {row, col, height}) into a priority queue and sort by height.
2. Poll each tree from the queue and use BFS to find out steps needed.

The worst case time complexity could be O(m^2 * n^2) (m = number of rows, n = number of columns) since there are m * n trees and for each BFS worst case time complexity is O(m * n) too.

class Solution {
    static int[][] dir = {{0,1}, {0, -1}, {1, 0}, {-1, 0}};

    public int cutOffTree(List<List<Integer>> forest) {
        if (forest == null || forest.size() == 0) return 0;
        int m = forest.size(), n = forest.get(0).size();

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (forest.get(i).get(j) > 1) {
                    pq.add(new int[] {i, j, forest.get(i).get(j)});
                }
            }
        }

        int[] start = new int[2];
        int sum = 0;
        while (!pq.isEmpty()) {
            int[] tree = pq.poll();
            int step = minStep(forest, start, tree, m, n);

            if (step < 0) return -1;
            sum += step;

            start[0] = tree[0];
            start[1] = tree[1];
        }

        return sum;
    }

    private int minStep(List<List<Integer>> forest, int[] start, int[] tree, int m, int n) {
        int step = 0;
        boolean[][] visited = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
        queue.add(start);
        visited[start[0]][start[1]] = true;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] curr = queue.poll();
                if (curr[0] == tree[0] && curr[1] == tree[1]) return step;

                for (int[] d : dir) {
                    int nr = curr[0] + d[0];
                    int nc = curr[1] + d[1];
                    if (nr < 0 || nr >= m || nc < 0 || nc >= n 
                        || forest.get(nr).get(nc) == 0 || visited[nr][nc]) continue;
                    queue.add(new int[] {nr, nc});
                    visited[nr][nc] = true;
                }
            }
            step++;
        }

        return -1;
    }

http://www.programmersought.com/article/222929242/

Give an int two-dimensional array representing the height of the tree at position i j , 0 is unreachable, 1 is flat. Cut the trees in order from short to high. Ask to take at least a few steps to finish.

Using a priority queue to find which tree we would cut. Using BFS to find the shortest steps. Using int[] store the postion and height of a tree. Add all of them into pq with ascending sorting.

Then preform BFS to find the steps needed to get the next position.

这道题让我们砍掉所有高度大于1的树，而且要求是按顺序从低到高来砍，那么本质实际上还是要求任意两点之间的最短距离啊。对于这种类似迷宫遍历求最短路径的题，BFS是不二之选啊。那么这道题就对高度相邻的两棵树之间调用一个BFS，所以我们可以把BFS的内容放倒子函数helper中来使用。那么我们首先就要将所有的树从低到高进行排序，我们遍历原二位矩阵，将每棵树的高度及其横纵坐标取出来，组成一个三元组，然后放到vector中，之后用sort对数组进行排序，因为sort默认是以第一个数字排序，这也是为啥我们要把高度放在第一个位置。然后我们就遍历我们的trees数组，我们的起始位置是（0，0），终点位置是从trees数组中取出的树的位置，然后调用BFS的helper函数，这个BFS的子函数就是很基本的写法，没啥过多需要讲解的地方，会返回最短路径的值，如果无法到达目标点，就返回-1。所以我们先检查，如果helper函数返回-1了，那么我们就直接返回-1，否则就将cnt加到结果res中。然后更新我们的起始点为当前树的位置，然后循环取下一棵树即可

https://www.acwing.com/solution/LeetCode/content/534/

你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个非负的二维数组表示，在这个数组中：

• 0 表示 障碍，无法触碰到。
• 1 表示可以行走的 地面。
• 比 1 大的数 表示一颗允许走过的 树 的，这个整数表示数的高度。

你被要求按照树的高度从低向高砍掉所有的树，每砍过一颗树，树的高度变为 1。

你将从（0，0）点开始工作，你应该返回你砍完所有树需要走的最小步数。如果你无法砍完所有的树，返回 -1 。

可以保证的是，没有两棵 树 的高度是相同的，并且至少有一颗树需要被砍。

1. 首先将所有的树和坐标放到一个数组中，并且按照高度从小到大排序。
2. 接着遍历每一棵树，并通过BFS计算出从上一棵树走到这一棵树需要的最少步数；若无法达到，则答案就是 -1。

https://leetcode.com/articles/cutoff-trees-for-golf-event/
http://reeestart.me/2018/04/22/LeetCode-675-Cut-Off-Trees-for-Golf-Event/

X, Videos
花花酱 LeetCode 675. Cut Off Trees for Golf Event - 刷题找工作 EP55