# Straightforward approach using C++ map and BFS

• straightforward solution to use the following two steps:

1. create a tree height => location map. since no two trees have the same height, so we can just use a map. otherwise, should use a multimap, which allows duplicate keys. When insert tree height and position pair into the map, it will be sorted automatically by map.
2. start from [0,0] using BFS approach to find the shortest path from the current position to the next tree position in the map. for the BFS approach, just use a queue to add the valid neighbors into the end of the queue.
``````static int row_offset[4] = {-1, 0, 1, 0};
static int col_offset[4] = {0, -1, 0, 1};

class Solution {
bool IsSamePos(int r, int c, int new_r, int new_c) {
return (r == new_r) && (c == new_c);
}
bool InBound(int r, int c, int rows, int cols)
{
return (r>=0) && (r<rows) && (c>=0) && (c<cols);
}

int FindPath(vector<vector<int>>& forest, int cur_r, int cur_c, int target_r, int target_c) {
if (IsSamePos(cur_r, cur_c, target_r, target_c))
return 0;

int row = forest.size();
int col = forest[0].size();
vector<vector<int>> path(row, vector<int>(col, INT_MAX));

queue<pair<int, int>> q;
q.push(make_pair(cur_r, cur_c));
path[cur_r][cur_c] = 0;

// use BFS approach to find the shortest path from the cur_r/c to any cell with non-zero.
while(!q.empty()) {
auto top = q.front();
int r = top.first;
int c = top.second;

if (IsSamePos(r, c, target_r, target_c)) {
return path[r][c];
}
for (int k=0; k<4; k++) {
int next_r = r + row_offset[k];
int next_c = c + col_offset[k];

if (IsSamePos(next_r, next_c, target_r, target_c)) {
path[next_r][next_c] = min(path[next_r][next_c], (path[r][c]+1));
q.push(make_pair(next_r, next_c));
} else if (InBound(next_r, next_c, row, col) && (path[next_r][next_c] == INT_MAX) && (forest[next_r][next_c] != 0)) {
path[next_r][next_c] = min(path[next_r][next_c], (path[r][c]+1));
q.push(make_pair(next_r, next_c));
}
}
q.pop();
}

return INT_MAX;
}

public:
int cutOffTree(vector<vector<int>>& forest) {
if (forest.size()==0) return -1;
int row = forest.size();
int col = forest[0].size();
if (forest[0][0] == 0) return -1;

imap<int, pair<int, int>> g;

// create a hash map from tree height to position.
for (int r = 0; r < row; r ++) {
for (int c = 0; c < col; c++) {
if (forest[r][c] != 0) {
g.insert(make_pair(forest[r][c], make_pair(r, c)));
}
}
}

int cur_r = 0, cur_c = 0;
int total_steps = 0;
//find path from one tree to the other following height increasing order.
while (!g.empty()) {
auto it = g.begin();
int r = (*it).second.first;
int c = (*it).second.second;
int steps = FindPath(forest, cur_r, cur_c, r, c);
if (steps != INT_MAX) {
forest[r][c] = 1;
g.erase(it);
total_steps += steps;
cur_r = r;
cur_c = c;
} else {
return -1;
}
}