c++ priority queue and BFS


  • 0
    J
    class Solution {
    private:
        int dirx[4] = {-1, 0, 1, 0};
        int diry[4] = {0, -1, 0, 1};
    public:
        int cutOffTree(vector<vector<int>>& forest) {
            if(forest.empty())
                return 0;
            int m = forest.size();
            int n = forest[0].size();
            
            priority_queue<int, vector<int>, std::greater<int>> TreesToCut;
            for(int i=0; i<m; i++)
            {
                for(int j=0; j<n; j++)
                {
                    if(forest[i][j] > 1)
                    {
                        
                        TreesToCut.push(forest[i][j]);
                    }
                        
                }
            }
            //if the starting point is the smallest, it doesn't need to take a step to cut this tree
            if(forest[0][0] == TreesToCut.top())
            {
                forest[0][0]=1;
                TreesToCut.pop();
            }
            int steps = 0;
            int orgx = 0;
            int orgy = 0; 
            while(!TreesToCut.empty())
            {
                int height = TreesToCut.top();
                TreesToCut.pop();
                int desx = 0;
                int desy = 0;
                int minStep = findMinSteps(forest, orgx, orgy, desx, desy, height);
                if(minStep == -1)
                    return -1;
                steps += minStep;
                orgx = desx;
                orgy = desy;
            }
            return steps;
        }
        
        int findMinSteps(vector<vector<int>>& forest, int orgx, int orgy, int& desx, int& desy, int height)
        {
            int m = forest.size();
            int n = forest[0].size();
            int steps = 0;
            queue<pair<int, int>> q;
            q.push(make_pair(orgx, orgy));
            vector<vector<bool>> visited(m, vector<bool>(n, false));
            while(!q.empty())
            {
                int sz = q.size();
                ++steps;
                for(int k=0; k<sz; k++)
                {
                    int curx = q.front().first;
                    int cury = q.front().second;
                    q.pop();
                    for(int i=0; i<4; i++)
                    {
                        int newx = curx + dirx[i];
                        int newy = cury + diry[i];
                        if(newx >= 0 && newx < m && newy >=0 && newy < n && forest[newx][newy] != 0 && visited[newx][newy] == false)
                        {
                            visited[newx][newy] = true;
                            if(forest[newx][newy] == height) //this is the tree that need to be cut;
                            {
                                forest[newx][newy] = 1;
                                desx = newx;
                                desy = newy;
                                return steps;
                            }
                            else
                            {
                                q.push(make_pair(newx, newy));
                            }
                        }
                    }
                }
            }
            return -1;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.