[675. Cut Off Trees for Golf Event] #leetcode

675_0929.java

class Solution {
    private final static int[][] dir = {{-1, 0} , {1, 0}, {0, 1}, {0, -1}};
        
    public int cutOffTree(List<List<Integer>> forest) {
        if (forest == null || forest.size() == 0) return 0; 
        
        int m = forest.size();
        int n = forest.get(0).size();
        
        // put trees in heap
        PriorityQueue<int[]> pq = new PriorityQueue<>(
            (x, y) -> x[2] - y[2]
        );
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int h = forest.get(i).get(j);
                if (h > 1) {
                    pq.add(new int[] {i, j, h});
                }
            }
        }
        
        // get minimal path for each tree
        int sum = 0;
        int[] start = new int[2];
        while (!pq.isEmpty()) {
            int[] tree = pq.poll();
            int steps = getMinStep(tree, start, m, n, forest);
            
            if (steps < 0) return -1;
            sum += steps;
            
            start[0] = tree[0];
            start[1] = tree[1];
        }
        
        return sum;
    }
    
    private static int getMinStep(int[] tree, int[] start, int m, int n, List<List<Integer>> forest) {
        int step = 0;
        Deque<int[]> q = new LinkedList<int[]>();
        boolean[][] visited = new boolean[m][n];
        visited[start[0]][start[1]] = true;
        
        
        
        q.addLast(start);
        while (!q.isEmpty()) {
            int length = q.size();
            
            for (int i = 0; i < length; i++) {
                int[] loc = q.removeFirst();
                if (loc[0] == tree[0] && loc[1] == tree[1]) return step;
                
                for (int[] d : dir) {
                    int x = loc[0] + d[0];
                    int y = loc[1] + d[1];
                    
                    if (x >= 0 && y >= 0 && x < m && y < n && !visited[x][y] && forest.get(x).get(y) != 0) {
                        q.addLast(new int[] {x, y});
                        visited[x][y] = true;
                    }
                }
            }
            
            step++;
        }
        
        return -1;
    }
}