Intuition

The key idea is to cut the trees in order of increasing height, always moving from the current position to the next tree using the shortest path. Since the grid is small, we can use BFS to find the shortest path between any two points, treating obstacles as impassable.

Approach

Collect all trees (cells with value > 1) and their positions, then sort them by height.
Start from (0, 0). For each tree in order:
- Use BFS to find the minimum steps from the current position to the tree's position.
- If a tree is unreachable, return -1.
- Move to the tree's position and set its cell to 1 (cut the tree).
Sum the steps for all trees and return the total.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int cutOffTree(vector<vector<int>>& forest) {\n        int m = forest.size(), n = forest[0].size();\n        vector<tuple<int, int, int>> trees;\n        for (int i = 0; i < m; ++i)\n            for (int j = 0; j < n; ++j)\n                if (forest[i][j] > 1)\n                    trees.emplace_back(forest[i][j], i, j);\n        sort(trees.begin(), trees.end());\n        auto bfs = [&](int sx, int sy, int tx, int ty) {\n            if (sx == tx && sy == ty) return 0;\n            vector<vector<int>> vis(m, vector<int>(n, 0));\n            queue<pair<int, int>> q;\n            q.push({sx, sy});\n            vis[sx][sy] = 1;\n            int d = 0;\n            int dirs[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};\n            while (!q.empty()) {\n                int sz = q.size();\n                ++d;\n                while (sz--) {\n                    auto [x, y] = q.front(); q.pop();\n                    for (auto& dir : dirs) {\n                        int nx = x + dir[0], ny = y + dir[1];\n                        if (nx >= 0 && nx < m && ny >= 0 && ny < n && !vis[nx][ny] && forest[nx][ny] != 0) {\n                            if (nx == tx && ny == ty) return d;\n                            vis[nx][ny] = 1;\n                            q.push({nx, ny});\n                        }\n                    }\n                }\n            }\n            return -1;\n        };\n        int ans = 0, cx = 0, cy = 0;\n        for (auto& [h, x, y] : trees) {\n            int d = bfs(cx, cy, x, y);\n            if (d == -1) return -1;\n            ans += d;\n            cx = x; cy = y;\n        }\n        return ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    int</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> cutOffTree</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">>></span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x26;</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> forest</s

Related Tags