Simple BFS + priority queue solution beats 90%
Approach -> Apply BFS from src node (initially (0,0))  to the smallest node with value >1. If there is no path then return -1. Else continue the iteration until
Approach -> Apply BFS from src node (initially (0,0))  to the smallest node with value >1. If there is no path then return -1. Else continue the iteration until you have cut all the trees in ascending order or you can\'t find a path anymore.\n\nclass Solution {\npublic:\n    bool is_valid(int x,int y,int n,int m,vector<vector<int>> &mat)\n    {\n        if(x<0 || x>=n || y<0 || y>=m || mat[x][y]==0)\n            return false;\n        \n        return true;\n    }\n    int cutOffTree(vector<vector<int>>& mat) {\n        \n        int n=mat.size();\n        int m=mat[0].size();\n        if(n==0)\n            return 0;\n        \n        if(mat[0][0]==0)\n            return -1;\n        int curr_x=0,curr_y=0;\n        int ans=0;\n        priority_queue<pair<int,pair<int,int>>> pq;\n        for(int i=0;i<n;i++)\n        {\n            for(int j=0;j<m;j++)\n            {\n                if(mat[i][j]>1)\n                pq.push({-mat[i][j],{i,j}});\n            }\n        }\n        bool vis[n][m];\n        while(!pq.empty())\n        {\n            pair<int,pair<int,int>> t=pq.top();\n            pq.pop();\n            int final_x=t.second.first;\n            int final_y=t.second.second;\n            queue<pair<int,int>> q;\n            q.push({curr_x,curr_y});\n            memset(vis,false,sizeof vis);\n            vis[curr_x][curr_y]=true;\n            int lvl=0;\n            int arr[]={1,0,-1,0};\n            int brr[]={0,1,0,-1};\n            bool ok=false;\n            while(!q.empty())\n            {\n                int si=q.size();\n                for(int i=0;i<si;i++)\n                {\n                    pair<int,int> s=q.front();\n                    q.pop();\n                    if(s.first==final_x && s.second==final_y)\n                    {\n                        ans+=lvl;\n                        ok=true;\n                        break;\n                    }\n                    for(int i=0;i<4;i++)\n                    {\n                       int x=s.first+arr[i];\n                       int y=s.second+brr[i];\n                       if(is_valid(x,y,n,m,mat))\n                       {\n                          if(vis[x][y]==false)\n                          {\n                            vis[x][y]=true;\n                            q.push({x,y});\n                          }\n                       }\n                    }\n                }\n                if(ok)\n                    break;\n                \n                lvl++;\n            }\n            if(ok==false)\n                return -1;\n            \n            curr_x=final_x;\n            curr_y=final_y;\n            \n        }\n        \n        return ans;\n    }\n};
[]