C++, Sort + BFS with explanation


  • 1
    Z

    The solution has two steps:

    1) Sort tree positions based on tree height; 
    2) BFS to find shortest path between two points; 
    

    The end point of current path is the starting point of next path. Priority_queue also works, but may be slower than simple sort due to both push and pop operations.

    The run time is up to O(m^2 n^2) where m and n is the matrix size.

    class Solution {
    public:
        int cutOffTree(vector<vector<int>>& forest) {
            if (forest.empty() || forest[0].empty()) return 0;
            int m = forest.size(), n = forest[0].size();
            vector<vector<int>> trees;
            // get all the tree positions and sort based on height
            // trees[i][0] is height. The default comparison of vector compare first element before other elements.
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (forest[i][j] > 1) trees.push_back({forest[i][j], i, j});
                }
            }
            sort(trees.begin(), trees.end());
            int ans = 0;
            // accumulate all the paths
            for (int i = 0, cur_row = 0, cur_col = 0; i < trees.size(); i++) {
                int step = next_step(forest, cur_row, cur_col, trees[i][1], trees[i][2]);
                // if next tree cannot be reached, step = -1;
                if (step == -1) return -1;
                ans += step;
                cur_row = trees[i][1];
                cur_col = trees[i][2];
            }
            return ans;
        }
    private:
        // BFS to find shortest path to next tree; if cannot reach next tree, return -1
        int next_step(vector<vector<int>>& forest, int sr, int sc, int er, int ec) {
            if (sr == er && sc == ec) return 0;
            int m = forest.size(), n = forest[0].size();
            queue<pair<int, int>> myq;
            myq.push({sr, sc}); 
            vector<vector<int>> visited(m, vector<int>(n, 0));
            visited[sr][sc] = 1;
            int step = 0;
            vector<int> dir = {-1, 0, 1, 0, -1};
            while (!myq.empty()) {
                step++;
                int sz = myq.size();
                for (int i = 0; i < sz; i++) {
                    int row = myq.front().first, col = myq.front().second;
                    myq.pop();
                    for (int i = 0; i < 4; i++) {
                        int r = row + dir[i], c = col + dir[i+1];
                        if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c] == 1 || forest[r][c] == 0) continue;
                        if (r == er && c == ec) return step;
                        visited[r][c] = 1;
                        myq.push({r, c});
                    }
                }
            }
            return -1;
        }
    };
    

  • 0
    B

    @zestypanda I think you miss to consider the case like

    {
    {1,5,0,3},
    {4,2,1,1}
    }

    you can't directly go to point (1,1) because of the '5' becoming the blocker.

    You may judge the
    if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c] == 1 || forest[r][c] == 0) continue;
    to
    if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c] == 1 || forest[r][c] != 1) continue;

    and add
    forest[trees[i][1]][trees[i][2]] = 1;
    when
    ans += step;


  • 0
    B

    @byxiangfei please ignore this, i was wrong, the question doesn't require '5' as the blocker, it still can walk through.


Log in to reply
 

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