# 0675. Cut Off Trees for Golf Event
###### tags: `Leetcode` `BFS` `Hard`
Link: https://leetcode.com/problems/cut-off-trees-for-golf-event/
## 思路 $O(M^2N^2)$ $O(MN)$
先给所有的tree按照height排序 然后依次用bfs找最短距离
## Code

class Solution {
    public int cutOffTree(List<List<Integer>> forest) {
        Queue<int[]> pq = new PriorityQueue<>((a,b)->(a[2]-b[2]));
        for(int i=0; i<forest.size(); i++){
            for(int j=0; j<forest.get(0).size(); j++){
                if(forest.get(i).get(j)>1){
                    pq.add(new int[]{i, j, forest.get(i).get(j)});
                }
            }
        }
        
        int[] start = new int[]{0,0};
        int steps = 0;
        int size = pq.size();
        for(int i=0; i<size; i++){
            int[] tree = pq.poll();
            int step = bfs(forest, start, tree);
            if(step==-1) return -1;
            steps += step;
            start = tree;
        }
        return steps;       
    }
    private int bfs(List<List<Integer>> forest, int[] start, int[] tree){
        boolean[][] visited = new boolean[forest.size()][forest.get(0).size()];
        int[][] dirs = new int[][]{{-1,0},{1,0},{0,1},{0,-1}};
        Queue<int[]> q = new LinkedList<>();
        q.add(start);
        visited[start[0]][start[1]] = true;
        int step = 0;
        while(!q.isEmpty()){
            int size = q.size();
            for(int i=0; i<size; i++){
                int[] curr = q.poll();
                if(curr[0]==tree[0] && curr[1]==tree[1]) return step;
                for(int[] dir:dirs){
                    int newx = curr[0]+dir[0];
                    int newy = curr[1]+dir[1];
                    if(newx>=0 && newx<forest.size() && newy>=0 && newy<forest.get(0).size() && forest.get(newx).get(newy)!=0 && !visited[newx][newy]){
                        visited[newx][newy] = true;
                        q.add(new int[]{newx, newy});
                    }
                }
            }
            step++;
        }
        return -1;
    }
}