675. Cut Off Trees for Golf Event

You are asked to cut off all the trees in a forest for a golf event. The forest is represented as an m x n matrix. In this matrix:

• 0 means the cell cannot be walked through.
• 1 represents an empty cell that can be walked through.
• A number greater than 1 represents a tree in a cell that can be walked through, and this number is the tree's height.

In one step, you can walk in any of the four directions: north, east, south, and west. If you are standing in a cell with a tree, you can choose whether to cut it off.

You must cut off the trees in order from shortest to tallest. When you cut off a tree, the value at its cell becomes 1 (an empty cell).

Starting from the point (0, 0), return the minimum steps you need to walk to cut off all the trees. If you cannot cut off all the trees, return -1.

Note: The input is generated such that no two trees have the same height, and there is at least one tree needs to be cut off.

Example 1:

Input: forest = [[1,2,3],[0,0,4],[7,6,5]]
Output: 6
Explanation: Following the path above allows you to cut off the trees from shortest to tallest in 6 steps.

Example 2:

Input: forest = [[1,2,3],[0,0,0],[7,6,5]]
Output: -1
Explanation: The trees in the bottom row cannot be accessed as the middle row is blocked.

Example 3:

Input: forest = [[2,3,4],[0,0,5],[8,7,6]]
Output: 6
Explanation: You can follow the same path as Example 1 to cut off all the trees.
Note that you can cut off the first tree at (0, 0) before making any steps.

Constraints:

• m == forest.length
• n == forest[i].length
• 1 <= m, n <= 50
• 0 <= forest[i][j] <= 109
• Heights of all trees are distinct.

Solution:

有点儿读不懂题系列

class Solution {
    int n;
    int m; 
    public int cutOffTree(List<List<Integer>> forest) {
        n = forest.size();
        m = forest.get(0).size();
        //1. find the shortest position
        //   -> priorityQueue  // -> tree need cut
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> (a[0] - b[0]));
        // int[] = nums, i, j
        int[][] matrix = new int[n][m]; // O(n * m )
        for (int i = 0; i < n; i++){
            List<Integer> curRow = forest.get(i);
            for (int j = 0; j < m; j++){
                int num = curRow.get(j);
                matrix[i][j] = num;

                if (num > 1){
                    pq.offer(new int[]{num, i, j}); // O(n * m logn)
                }

            }
        }
        //         2. start cur position to find the shortest path to the next one 
           // -> bfs

        int pre_i = 0;
        int pre_j = 0;
        int steps = 0;

        while(!pq.isEmpty()){
            int[] cur = pq.poll();
            int shortestPath = bfs(pre_i, pre_j, matrix, cur[1], cur[2]);
            if (shortestPath == -1){
                return -1;
            }

            steps = steps + shortestPath;
            pre_i = cur[1];
            pre_j = cur[2];
        }

        return steps;
    }

    private int bfs(int pre_i, int pre_j, int[][] matrix, int tx, int ty){
        // queue
        Deque<int[]> queue = new ArrayDeque<>();

        boolean[][] visited = new boolean[n][m];
        visited[pre_i][pre_j] = true;
        queue.offerLast(new int[]{pre_i, pre_j});

        int result = 0;

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

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

                int x = cur[0];
                int y = cur[1];

                if (x == tx && y == ty){
                    return result;
                }

                for (int[] dir : dirs){
                    int nx = x + dir[0];
                    int ny = y + dir[1];

                    if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && matrix[nx][ny] != 0){
                        queue.offerLast(new int[]{nx, ny});
                        visited[nx][ny] = true;// avoid go back
                    }

                }
            }

            result++;
        }
        return -1;

    }
}

        /*
        2 3 4
        0 0 5
        1 7 6


        2 - 3 - 4 
                |
                5
                |
       *1* - 7 - 6      -> 6 step


       cut 1
           -   -
       *2* - 3 - 4 
                | |
                5  
                | |
       1√ - 7 - 6      -> find the 2nd shortest -> 6 steps -> 2
         ->   ->  
                       total : 12


        17 steps



        high level:
        1. find the shortest position
           -> priorityQueue 
        2. start cur position to find the shortest path to the next one 
            -> bfs
        3. every tree be cut -> finish
            -> return steps(global)

        */


// TC: O(n *m logn)
// SC: O(n *m )