Straightforward approach using C++ map and BFS


  • 0
    Z

    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;
                }
            }
            return total_steps;
        }
    };
    

Log in to reply
 

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