# c++ priority queue and BFS

• ``````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;
}
};
``````

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