# 675 Cut Off Trees for Golf Event

## 675 Cut Off Trees for Golf Event

## 1. Question

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.

## 2. Implementation

**(1) PriorityQueue + BFS**

思路:

```java
class Solution {
    public int cutOffTree(List<List<Integer>> forest) {
        if (forest.size() == 0 && forest.get(0).size() == 0) {
            return -1;
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b)->(a[2] - b[2]));
        int m = forest.size(), n = forest.get(0).size();

        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[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int[] start = {0, 0};
        int res = 0;
        while (!pq.isEmpty()) {
            int[] destination = pq.remove();
            int steps = getStepsByBFS(start, destination, m, n, directions, forest);

            if (steps < 0) {
                return -1;
            }

            res += steps;
            start[0] = destination[0];
            start[1] = destination[1];
        }
        return res;
    }

    public int getStepsByBFS(int[] start, int[] dest, int m, int n, int[][] directions, List<List<Integer>> forest) {
        boolean[][] visited = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
        queue.add(start);
        visited[start[0]][start[1]] = true;
        int steps = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] curCell = queue.remove();

                if (curCell[0] == dest[0] && curCell[1] == dest[1]) {
                    return steps;
                }

                for (int[] direction : directions) {
                    int nextRow = curCell[0] + direction[0];
                    int nextCol = curCell[1] + direction[1];

                    if (isValid(m, n, nextRow, nextCol, visited, forest)) {
                        queue.add(new int[] {nextRow, nextCol});
                        visited[nextRow][nextCol] = true;
                    }
                }
            }
            ++steps;
        }
        return -1;
    }

    public boolean isValid(int rows, int cols, int curRow, int curCol, boolean[][] visited, List<List<Integer>> forest) {
        return curRow >= 0 && curRow < rows && curCol >= 0 && curCol < cols && !visited[curRow][curCol] && forest.get(curRow).get(curCol) > 0;
    }
}
```

## 3. Time & Space Complexity

**PriorityQueue + BFS: 时间复杂度O(m^2n^2), 空间复杂度O(m^2n^2)**