C++ Simple (BFS+ PriorityQueue) Solution With Explanation
Approach:\nWhat we are being told is we want to cut trees in such a manner:\n1. We want to cut the trees in increasing order of their heights\n2. We can travers
Approach:\nWhat we are being told is we want to cut trees in such a manner:\n1. We want to cut the trees in increasing order of their heights\n2. We can traverse through nodes with value > 1 \n\nAnd we want to minimise the number of steps to cut all trees.\nMin no. of steps to cut all trees = (min. no of steps from (0,0) to smallest tree + min. no of steps from smallest tree to second smallest tree+.... )\n\nIn order to find the next smallest tree, we use priority queue and\nin order to find min. no. of steps from (i,j) to (u,v) we use BFS.\n```\n#define p pair<int,pair<int,int>>\nclass Solution {\npublic:\n    int m,n;\n    int bfs(int &i,int &j,int &u,int &v,vector<vector<int>>& nums){\n        vector<vector<bool>>explored(m,vector<bool>(n,false));\n        bool found=false;\n        queue<pair<int,int>>q;\n        q.push({i,j});\n        explored[i][j]=true;\n        int cnt=0;\n        while(!q.empty()){\n            int l=q.size();\n            while(l--){\n                pair<int,int>a=q.front();\n                int x=a.first,y=a.second;\n                q.pop();\n                if(x==u && y==v){\n                    found=true;\n                    break;\n                }\n                if(x>0 && nums[x-1][y] && !explored[x-1][y]){\n                    explored[x-1][y]=true;\n                    q.push({x-1,y});\n                }\n                if(y>0 && nums[x][y-1] && !explored[x][y-1]){\n                    explored[x][y-1]=true;\n                    q.push({x,y-1});\n                }\n                if(x<m-1 && nums[x+1][y] && !explored[x+1][y]){\n                    explored[x+1][y]=true;\n                    q.push({x+1,y});\n                }\n                if(y<n-1 && nums[x][y+1] && !explored[x][y+1]){\n                    explored[x][y+1]=true;\n                    q.push({x,y+1});\n                }\n            }\n            if(found)\n                break;\n            cnt++;\n        }\n        return found?cnt:-1;\n    }\n    int cutOffTree(vector<vector<int>>& nums) {\n        m=nums.size(),n=nums[0].size();\n        priority_queue<p,vector<p>,greater<p>>q;\n        for(int i=0;i<m;i++){\n            for(int j=0;j<n;j++){\n                if(nums[i][j]>1)\n                    q.push({nums[i][j],{i,j}});\n            }\n        }\n        int i=0,j=0,ans=0;\n        while(!q.empty()){\n            p a=q.top();\n            int u=a.second.first,v=a.second.second;\n            q.pop();\n            int b=bfs(i,j,u,v,nums);\n            if(b==-1)\n                return -1;\n            i=u,j=v;\n            ans+=b;\n        }\n        return ans;\n    }\n};\n```
['Breadth-First Search', 'C', 'Heap (Priority Queue)']