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.

&nbsp;
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.


&nbsp;
Constraints:


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


from collections import deque

class Solution:
    def cutOffTree(self, forest: List[List[int]]) -> int:
        a = []
        n = len(forest)
        m = len(forest[0])
        for i in range(n):
            for j in range(m):
                if forest[i][j] > 1:
                    a.append(forest[i][j])
        a.sort()
        
        s = 0
        ux = 0
        uy = 0
        for h in a:
            dist = [[None] * m for i in range(n)]
            q = deque()
            q.append((ux, uy))
            dist[ux][uy] = 0
            while q:
                ux, uy = q.popleft()
                if forest[ux][uy] == h:
                    break
                d = [(-1, 0), (0, 1), (1, 0), (0, -1)]
                for dx, dy in d:
                    vx = ux + dx
                    vy = uy + dy
                    if vx < 0 or vx >= n or vy < 0 or vy >= m:
                        continue
                    if forest[vx][vy] == 0:
                        continue
                    if dist[vx][vy] is None:
                        q.append((vx, vy))
                        dist[vx][vy] = dist[ux][uy] + 1
            if forest[ux][uy] == h:
                s += dist[ux][uy]
            else:
                return -1
        return s
class Solution {
    //approach: 1st store all the positions in the min heap acc. to their height
    //now start removing the elements from the heap and calculate their dis using bfs
    // if at any point we cann't reach at the next position return -1;
    // else keep on adding the distances and return;
    public int cutOffTree(List<List<Integer>> forest) {
       PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->(forest.get(a[0]).get(a[1])-forest.get(b[0]).get(b[1])));
       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});
           }
       }
        int ans=0;
       int curr[]={0,0};
       while(pq.size()>0){
           int[] temp=pq.poll();
           int dis=calcDis(forest,curr,temp);
           //System.out.println(dis+" "+temp.height);
           if(dis==-1)
               return -1;
           ans+=dis;
           curr=temp;
       }
        return ans;
    }
    int calcDis(List<List<Integer>> forest,int start[],int end[]){
        int n=forest.size(),m=forest.get(0).size();
        boolean vis[][]=new boolean[n][m];
        Queue<int[]> queue=new LinkedList<>();
        queue.add(start);
        vis[start[0]][start[1]]=true;
        int dis=0;
        while(queue.size()>0){
            int len =queue.size();
            while(len-->0){
                int temp[]=queue.remove();
                int r=temp[0],c=temp[1];
                if(r==end[0] && c==end[1])
                    return dis;
                if(r+1<n && !vis[r+1][c] && forest.get(r+1).get(c)!=0){
                    queue.add(new int[]{r+1,c});
                    vis[r+1][c]=true;
                }if(r-1>=0 && !vis[r-1][c] && forest.get(r-1).get(c)!=0){
                    queue.add(new int[]{r-1,c});
                    vis[r-1][c]=true;
                }if(c-1>=0 && !vis[r][c-1] && forest.get(r).get(c-1)!=0){
                    queue.add(new int[]{r,c-1});
                    vis[r][c-1]=true;
                }if(c+1<m && !vis[r][c+1] && forest.get(r).get(c+1)!=0){
                    queue.add(new int[]{r,c+1});
                    vis[r][c+1]=true;
                }
            }
            dis++;
        }
        return -1;
        
    }
}
class Solution {
public:
    
    #define vi vector<int>
    #define vvi vector<vi>
    
    vvi forests;
    vvi moves;
    int R;
    int C;
    
    
    bool isValid(int x,int y){
        return x>=0&&x<R&&y>=0&&y<C;
    }
    
    int getShortestDistance(int sx,int sy,int ex,int ey){
        
        vvi vis = vvi(R,vi(C,0));
        queue<pair<int,int>>Q;
        Q.push({sx,sy});
        
        vis[sx][sy] = 1;
                
        
        int level = 0;
        
        while(!Q.empty()){
            
            queue<pair<int,int>>childQ;
            
            while(!Q.empty()){
                
                auto x = Q.front().first;
                auto y = Q.front().second;
                
                Q.pop();
                
                if(x==ex&&y==ey)
                    return level;
                
                for(auto ele:moves){
                    
                    int nextX = x+ele[0];
                    int nextY = y+ele[1];
                    
                    if(isValid(nextX,nextY)&&!vis[nextX][nextY]&&forests[nextX][nextY]>0){
                        childQ.push({nextX,nextY});
                        vis[nextX][nextY]=1;
                    }
                    
                }
                
                
            }
            Q=childQ;
               
            level++;
        }
        
        return -1;
    }
    
    int cutOffTree(vector<vector<int>>& forest) {
        
        moves={
            {0,1},
            {1,0},
            {0,-1},
            {-1,0}
        };
        
        forests = forest;
        
        R = forest.size();
        C = forest[0].size();
        
        if(forest[0][0]==0)
            return -1;
        
        vector<vector<int>>trees;
        int i=0;
        
        while(i<R){
            int j=0;
            while(j<C){
                if(forest[i][j]>1)
                    trees.push_back({forest[i][j],i,j});
                
                j++;
            }
            i++;
        }
        
        if(trees.empty())
            return -1;
        
        sort(trees.begin(),trees.end());
        
        int sx = 0;
        int sy = 0;
        
        int ans = 0;
        
        for(auto it:trees){
            
            int dis = getShortestDistance(sx,sy,it[1],it[2]);
            
            if(dis==-1)
                return -1;
            ans+=dis;
            sx = it[1];
            sy = it[2];
        }
        
        return ans;
        
    }
};
var cutOffTree = function(forest) {
    const trees = forest.flat().filter(x => x && x !== 1).sort((a, b) => b - a);
    let currPos = [0, 0], totalDist = 0;

    while(trees.length) {
        const grid = [...forest.map(row => [...row])];
        const res = getDist(currPos, trees.pop(), grid);
        if(res == null) return -1;
        const [pos, dist] = res;
        currPos = pos;
        totalDist += dist;
    }
    return totalDist;    
    
    function getDist(start, target, grid) {
        const dir = [[1, 0], [-1, 0], [0, 1], [0, -1]];
        let queue = [start], dist = 0;
        
        while(queue.length) {
            const next = [];
            
            for(let [r, c] of queue) {
                if(grid[r][c] === target) return [[r, c], dist];
                if(!grid[r][c]) continue;
                
                for(let [x, y] of dir) {
                    x += r; y += c;
                    if(x >= 0 && x < grid.length && y >= 0 && 
                       y < grid[0].length && grid[x][y]) next.push([x, y])
                }
                grid[r][c] = 0;   
            }
            dist++;
            queue = next;
        }
        return null;
    }
};
Cut Off Trees for Golf Event