C++, Sort + BFS with explanation
The solution has two steps:\n\n1) Sort tree positions based on tree height; \n2) BFS to find shortest path between two points; \n\nThe end point of current path
The solution has two steps:\n```\n1) Sort tree positions based on tree height; \n2) BFS to find shortest path between two points; \n```\nThe 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.\n\nThe run time is up to O(m^2 n^2) where m and n is the matrix size. \n```\nclass Solution {\npublic:\n    int cutOffTree(vector<vector<int>>& forest) {\n        if (forest.empty() || forest[0].empty()) return 0;\n        int m = forest.size(), n = forest[0].size();\n        vector<vector<int>> trees;\n        // get all the tree positions and sort based on height\n        // trees[i][0] is height. The default comparison of vector compare first element before other elements.\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                if (forest[i][j] > 1) trees.push_back({forest[i][j], i, j});\n            }\n        }\n        sort(trees.begin(), trees.end());\n        int ans = 0;\n        // accumulate all the paths\n        for (int i = 0, cur_row = 0, cur_col = 0; i < trees.size(); i++) {\n            int step = next_step(forest, cur_row, cur_col, trees[i][1], trees[i][2]);\n            // if next tree cannot be reached, step = -1;\n            if (step == -1) return -1;\n            ans += step;\n            cur_row = trees[i][1];\n            cur_col = trees[i][2];\n        }\n        return ans;\n    }\nprivate:\n    // BFS to find shortest path to next tree; if cannot reach next tree, return -1\n    int next_step(vector<vector<int>>& forest, int sr, int sc, int er, int ec) {\n        if (sr == er && sc == ec) return 0;\n        int m = forest.size(), n = forest[0].size();\n        queue<pair<int, int>> myq;\n        myq.push({sr, sc}); \n        vector<vector<int>> visited(m, vector<int>(n, 0));\n        visited[sr][sc] = 1;\n        int step = 0;\n        vector<int> dir = {-1, 0, 1, 0, -1};\n        while (!myq.empty()) {\n            step++;\n            int sz = myq.size();\n            for (int i = 0; i < sz; i++) {\n                int row = myq.front().first, col = myq.front().second;\n                myq.pop();\n                for (int i = 0; i < 4; i++) {\n                    int r = row + dir[i], c = col + dir[i+1];\n                    if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c] == 1 || forest[r][c] == 0) continue;\n                    if (r == er && c == ec) return step;\n                    visited[r][c] = 1;\n                    myq.push({r, c});\n                }\n            }\n        }\n        return -1;\n    }\n};\n```
[]