C++ Beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    static constexpr int DIR[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};\n    struct Cell {\n        short r : 8;\n        short c : 8;\n    };\n    int doit(const vector<vector<int>>& forest, Cell start, vector<int> &curr, vector<int> &prev, vector<Cell> &bfs) {\n        const int M = forest.size(), N = forest[0].size();\n        int steps = 0;\n        swap(curr, prev);\n        fill(begin(curr), end(curr), -1);\n        curr[start.r * N + start.c] = steps;\n        if (prev[start.r * N + start.c] != -1) {\n            return prev[start.r * N + start.c];\n        }\n        bfs.clear();\n        bfs.push_back(start);\n        while (!bfs.empty()) {\n            int size = bfs.size();\n            steps++;\n            while (size--) {\n                auto [r0, c0] = bfs[size];\n                swap(bfs[size], bfs.back());\n                bfs.pop_back();\n                for (auto [dr, dc] : DIR) {\n                    short r1 = r0 + dr, c1 = c0 + dc;\n                    int pos = r1 * N + c1;\n                    if (r1 >= 0 && r1 < M && c1 >= 0 && c1 < N && forest[r1][c1] > 0 && curr[pos] == -1) {\n                        if (prev[pos] != -1) {\n                            return steps + prev[pos];\n                        }\n                        curr[pos] = steps;\n                        bfs.push_back({r1, c1});\n                    }\n                }\n            }\n        }\n        return -1;\n    }\n    int manhattan_distance(vector<Cell> &cells) {\n        int result = 0;\n        Cell prev{0, 0};\n        for (auto &cell : cells) {\n            result += abs(prev.r - cell.r) + abs(prev.c - cell.c);\n            prev = cell;\n        }\n        return result;\n    }\npublic:\n    int cutOffTree(vector<vector<int>>& forest) {\n        const int M = forest.size(), N = forest[0].size();\n        if (forest[0][0] == 0) {\n            return -1;\n        }\n        int obstacles = 0;\n        vector<Cell> cells;\n        cells.reserve(8);\n\n        for (short r = 0; r < M; r++) {\n            for (short c = 0; c < N; c++) {\n                if (forest[r][c] > 1) {\n                    cells.push_back({r, c});\n                } else if (forest[r][c] == 0) {\n                    obstacles++;\n                }\n            }\n        }\n        sort(begin(cells), end(cells), [&forest](const Cell &a, const Cell &b){\n            return forest[a.r][a.c] < forest[b.r][b.c];\n        });\n        if (obstacles == 0) {\n            return manhattan_distance(cells);\n        }\n        vector<int> curr(M * N, -1), prev = curr;\n        curr[0] = 0;\n\n        vector<Cell> bfs;\n        bfs.reserve(8);\n\n        int steps = 0;\n\n        for (auto &cell : cells) {\n            int result = doit(forest, cell, curr, prev, bfs);\n\n            if (result != -1) {\n                steps += result;\n            } else {\n                return -1;\n            }\n        }\n        return steps;\n    }\n};\n```
['C++']