Solution
C++ []\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    
```C++ []\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```\n\n```Python3 []\nclass Solution:\n    def cutOffTree(self, forest: List[List[int]]) -> int:\n        if forest[0][0] == 0 :\n            return -1\n        m = len(forest)\n        n = len(forest[0])\n        def distance(node1, node2):\n            now = [node1]\n            soon = []\n            expanded = set()\n            manhattan = abs(node1[0] - node2[0]) + abs(node1[1] - node2[1])\n            detours = 0\n            while True:\n                if len(now) == 0:\n                    now = soon\n                    soon = []\n                    detours += 1\n                node = now.pop()\n                if node == node2:\n                    return manhattan + 2 * detours\n                if node not in expanded:\n                    expanded.add(node)\n                    x, y = node\n                    if x - 1 >= 0 and forest[x - 1][y] >= 1:\n                        if x > node2[0]:\n                            now.append((x - 1, y))\n                        else:\n                            soon.append((x - 1, y))\n                    if y + 1 < n and forest[x][y + 1] >= 1:\n                        if y < node2[1]:\n                            now.append((x, y + 1))\n                        else:\n                            soon.append((x, y + 1))\n                    if x + 1 < m and forest[x + 1][y] >= 1:\n                        if x < node2[0]:\n                            now.append((x + 1, y))\n                        else:\n                            soon.append((x + 1, y))\n                    if y - 1 >= 0 and forest[x][y - 1] >= 1:\n                        if y > node2[1]:\n                            now.append((x, y - 1))\n                        else:\n                            soon.append((x, y - 1))\n        trees = []\n        for i in range(m):\n            for j in range(n):\n                if forest[i][j] > 1:\n                    trees.append(((i, j), forest[i][j]))\n        trees.sort(key=lambda x: x[1])\n        can_reach = {(0, 0)}\n        stack = [(0, 0)]\n        while len(stack) > 0:\n            x, y = stack.pop()\n            if x - 1 >= 0 and forest[x - 1][y] >= 1 and (x - 1, y) not in can_reach:\n                can_reach.add((x - 1, y))\n                stack.append((x - 1, y))\n            if y + 1 < n and forest[x][y + 1] >= 1 and (x, y + 1) not in can_reach:\n                can_reach.add((x, y + 1))\n                stack.append((x, y + 1))\n            if x + 1 < m and forest[x + 1][y] >= 1 and (x + 1, y) not in can_reach:\n                can_reach.add((x + 1, y))\n                stack.append((x + 1, y))\n            if y - 1 >= 0  and forest[x][y - 1] >= 1 and (x, y - 1) not in can_reach:\n                can_reach.add((x, y - 1))\n                stack.append((x, y - 1))\n        for t in trees:\n            if t[0] not in can_reach:\n                return -1\n        start = (0, 0)\n        num_step = 0\n        for t in trees: \n            num_step += distance(start, t[0])\n            forest[t[0][0]][t[0][1]] = 1\n            start = t[0]\n        return num_step\n```\n\n```Java []\nclass Solution {\n    public int cutOffTree(List<List<Integer>> forest) {\n        PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->(forest.get(a[0]).get(a[1])-forest.get(b[0]).get(b[1])));\n        for(int i=0;i<forest.size();i++){\n            for(int j=0;j<forest.get(0).size();j++){\n                if(forest.get(i).get(j)>1)\n                    pq.add(new int[]{i,j});\n            }\n        }\n        int ans=0;\n        int curr[]={0,0};\n        while(pq.size()>0){\n            int[] temp=pq.poll();\n            int dis=calcDis(forest,curr,temp);\n            if(dis==-1)\n                return -1;\n            ans+=dis;\n            curr=temp;\n        }\n        return ans;\n    }\n    int calcDis(List<List<Integer>> forest,int start[],int end[]){\n        int n=forest.size(),m=forest.get(0).size();\n        boolean vis[][]=new boolean[n][m];\n        Queue<int[]> queue=new LinkedList<>();\n        queue.add(start);\n        vis[start[0]][start[1]]=true;\n        int dis=0;\n        while(queue.size()>0){\n            int len =queue.size();\n            while(len-->0){\n                int temp[]=queue.remove();\n                int r=temp[0],c=temp[1];\n                if(r==end[0] && c==end[1])\n                    return dis;\n                if(r+1<n && !vis[r+1][c] && forest.get(r+1).get(c)!=0){\n                    queue.add(new int[]{r+1,c});\n                    vis[r+1][c]=true;\n                }if(r-1>=0 && !vis[r-1][c] && forest.get(r-1).get(c)!=0){\n                    queue.add(new int[]{r-1,c});\n                    vis[r-1][c]=true;\n                }if(c-1>=0 && !vis[r][c-1] && forest.get(r).get(c-1)!=0){\n                    queue.add(new int[]{r,c-1});\n                    vis[r][c-1]=true;\n                }if(c+1<m && !vis[r][c+1] && forest.get(r).get(c+1)!=0){\n                    queue.add(new int[]{r,c+1});\n                    vis[r][c+1]=true;\n                }\n            }\n            dis++;\n        }\n        return -1;\n    }\n}\n```\n
['C++', 'Java', 'Python3']