Problem Explanation

The goal of this problem is to cut all trees in a 2D forest. The forest is represented as a 2D map in which 0 represents an obstacle that can't be reached, 1 represents walk-able ground and numbers greater than 1 represent tree heights.

Start by cutting the tree with the shortest height first and repeat this process until all trees are cut down. After cutting a tree, the tree's position turns into walk-able ground (value 1). The starting position is (0,0) and we need to calculate the minimum number of steps needed to cut all trees. However, if there is a situation where not all trees can be cut, we will return -1.

Each tree has unique height and there must be at least one tree to cut.

Example Walkthrough

Given the input:

1[
2 [2,3,4],
3 [0,0,5],
4 [8,7,6]
5]

From point (0,0), we can cut the tree there directly first since its the shortest. The forest becomes:

1[
2 [1,3,4],
3 [0,0,5],
4 [8,7,6]
5]

Next we walk to the tree with height 3 which is just one step away, then cut it. The forest becomes:

1[
2 [1,1,4],
3 [0,0,5],
4 [8,7,6]
5]

Next we walk two steps to the tree with height 4 and cut it. The forest now becomes:

1[
2 [1,1,1],
3 [0,0,5],
4 [8,7,6]
5]

Now take 1 step back to the position (0,1) and then 2 steps downwards, reaching the tree with height now 5. Cut it and the forest is:

1[
2 [1,1,1],
3 [0,0,1],
4 [8,7,6]
5]

Finally, by walking 2 more steps to the right, we can reach and cut the tree of height 6. The total number of steps are 6, so the output is 6.

Solution Approach

This is a tree traversal problem. A priority queue is used to store all trees in a increasing order, as smaller heap tree represents a tree with smaller height.

Furthermore, the method BFS is used to implement the traversing between two points, including around the obstacles.

Python Solution

1
2python
3from queue import PriorityQueue
4class Solution:
5    def cutOffTree(self, forest: List[List[int]]) -> int:
6        if not forest or not forest[0]: return -1
7        m, n = len(forest), len(forest[0])
8        trees = sorted((v, i, j) for i, row in enumerate(forest) for j, v in enumerate(row) if v > 1)
9        sr = sc = ans = 0
10        for _, tr, tc in trees:
11            d = self.bfs(forest, sr, sc, tr, tc)
12            if d < 0: return -1
13            ans += d
14            sr, sc = tr, tc
15        return ans
16
17    def bfs(self, forest, sr, sc, tr, tc):
18        m, n = len(forest), len(forest[0])
19        visited = [[False] * n for _ in range(m)]
20        visited[sr][sc] = True
21        q = deque([(sr, sc, 0)])
22        while q:
23            r, c, d = q.popleft()
24            if r == tr and c == tc:
25                return d
26            for nr, nc in ((r-1,c), (r+1,c), (r,c-1), (r,c+1)):
27                if 0 <= nr < m and 0 <= nc < n and not visited[nr][nc] and forest[nr][nc]:
28                    visited[nr][nc] = True
29                    q.append((nr, nc, d+1))
30        return -1

Java Solution

1
2java
3class Solution {
4    public int cutOffTree(List<List<Integer>> forest) {
5        List<int[]> trees = new ArrayList<>();
6        for (int i = 0; i < forest.size(); ++i) {
7            for (int j = 0; j < forest.get(0).size(); ++j) {
8                int value = forest.get(i).get(j);
9                if (value > 1) trees.add(new int[] { value, i, j });
10            }
11        }
12        Collections.sort(trees, (a, b) -> Integer.compare(a[0], b[0]));
13        int ans = 0, sr = 0, sc = 0;
14        for (int[] tree: trees) {
15            int tr = tree[1], tc = tree[2];
16            int d = bfs(forest, sr, sc, tr, tc);
17            if (d < 0) return -1;
18            ans += d;
19            sr = tr; sc = tc;
20        }
21        return ans;
22    }
23
24    public int bfs(List<List<Integer>> forest, int sr, int sc, int tr, int tc) {
25        int R = forest.size(), C = forest.get(0).size();
26        Queue<int[]> queue = new LinkedList<>();
27        queue.offer(new int[]{sr,sc,0});
28        boolean[][] visited = new boolean[R][C];
29        visited[sr][sc] = true;
30        while(!queue.isEmpty()){
31            int[] cu = queue.poll();
32            if(cu[0]==tr && cu[1] == tc){
33                return cu[2];
34            }else{
35                for(int[] dir:dirs){
36                    int nr = cu[0] + dir[0];
37                    int nc = cu[1] + dir[1];
38                    if(isValid(nr,nc,R,C) && forest.get(nr).get(nc) > 0 && !visited[nr][nc]){
39                        queue.offer(new int[]{nr,nc,cu[2]+1});
40                        visited[nr][nc]=true;
41                    }
42                }
43            }
44        }
45        return -1;
46    }
47}

C++ Solution

1
2cpp
3class Solution {
4public:
5    int cutOffTree(vector<vector<int>>& forest) {
6        int m = forest.size(), n = forest[0].size();
7        vector<vector<int>> trees;
8        for (int i = 0; i < m; ++i) {
9            for (int j = 0; j < n; ++j) {
10                if (forest[i][j] > 1) trees.push_back({forest[i][j], i, j});
11            }
12        }
13        sort(trees.begin(), trees.end());
14        int ans = 0;
15        for (int i = 0, curx = 0, cury = 0; i < trees.size(); ++i) {
16            int tx = trees[i][1], ty = trees[i][2];
17            int step = minStep(forest, curx, cury, tx, ty);
18            if (step == -1) return -1;
19            ans += step;
20            curx = tx, cury = ty;
21        }
22        return ans;
23    }
24private:
25    int minStep(vector<vector<int>>& forest, int sr, int sc, int er, int ec) {
26        int m = forest.size(), n = forest[0].size();
27        queue<pair<int, int>> q;
28        vector<vector<int>> visited(m, vector<int>(n, 0));
29        vector<int> dir{-1, 0, 1, 0, -1};
30        q.push({sr, sc});
31        visited[sr][sc] = 1;
32        for (int d = 0; !q.empty(); ++d) {
33            for (int sz = q.size(); sz > 0; --sz) {
34                int x = q.front().first, y = q.front().second;
35                q.pop();
36                if (x == er && y == ec) return d;
37                for (int i = 0; i < 4; ++i) {
38                    int tx = x + dir[i], ty = y + dir[i + 1];
39                    if (tx >= 0 && tx < m && ty >= 0 && ty < n && !visited[tx][ty] && forest[tx][ty] >= 1) {
40                        visited[tx][ty] = 1;
41                        q.push({tx, ty});
42                    }
43                }
44            }
45        }
46        return -1;
47    }
48};

C# Solution

1
2csharp
3public class Solution {
4    public int CutOffTree(IList<IList<int>> forest) {
5        List<int[]> trees = new List<int[]>();
6        for (int r = 0; r < forest.Count; ++r) {
7            for (int c = 0; c < forest[0].Count; ++c) {
8                int v = forest[r][c];
9                if (v > 1) trees.Add(new int[]{v, r, c});
10            }
11        }
12        trees.Sort((a, b) => a[0]-b[0]);
13        int ans = 0, sr = 0, sc = 0;
14        foreach (int[] tree in trees) {
15            int d = Bfs(forest, sr, sc, tree[1], tree[2]);
16            if (d < 0) return -1;
17            ans += d;
18            sr = tree[1]; sc = tree[2];
19        }
20        return ans;
21    }
22    
23    public int Bfs(IList<IList<int>> forest, int sr, int sc, int tr, int tc) {
24        int R = forest.Count, C = forest[0].Count;
25        Queue<int[]> queue = new Queue<int[]>();
26        queue.Enqueue(new int[]{sr,sc,0});
27        int[][] seen = new int[R][];
28        for(int i = 0; i < R; ++i) {
29            seen[i] = new int[C];
30        }
31        seen[sr][sc] = 1;
32        while(queue.Count > 0) {
33            int[] cur = queue.Dequeue();
34            if (cur[0] == tr && cur[1] == tc) return cur[2];
35            for (int di = 0; di < 4; ++di) {
36                int r = cur[0] + dr[di];
37                int c = cur[1] + dc[di];
38                if (0 <= r && r < R && 0 <= c && c < C &&
39                    forest[r][c] > 0 && seen[r][c] == 0) {
40                    seen[r][c] = 1;
41                    queue.Enqueue(new int[]{r, c, cur[2]+1});
42                }
43            }
44        }
45        return -1;
46    }
47}

JavaScript Solution

1
2javascript
3var cutOffTree = function(forest) {
4    if (forest[0][0] === 0)  return -1;
5    const m = forest.length, n = forest[0].length;
6    const sortedHeights = [];
7    for (let i = 0; i < m; i++) {
8        for (let j = 0; j < n; j++) {
9            const h = forest[i][j];
10            if (h > 1)  sortedHeights.push({h, i, j});
11        }
12    }
13    sortedHeights.sort((a, b) => a.h - b.h);
14    
15    const direction = [[0, 1], [1, 0], [0, -1], [-1, 0]];
16    let result = 0, start = [0, 0];
17    for (let tree of sortedHeights) {
18        let step = bfs(forest, start, [tree.i, tree.j]);
19        if (step === -1)  return -1;
20        result += step;
21        start = [tree.i, tree.j];
22    }
23    
24    function bfs(forest, start, end) {
25        let visited = Array.from({length: m}, () => Array(n).fill(0));
26        let queue = [start];
27        visited[start[0]][start[1]] = 1;
28        let step = 0;
29        while (queue.length) {
30            let len = queue.length;
31            while (len--) {
32                let [i, j] = queue.shift();
33                if (i === end[0] && j === end[1])  return step;
34                for (let d of direction) {
35                    let ni = i + d[0], nj = j + d[1];
36                    if (ni < 0 || nj < 0 || ni >= m || nj >= n || visited[ni][nj] || forest[ni][nj] === 0)  continue;
37                    queue.push([ni, nj]);
38                    visited[ni][nj] = 1;
39                }
40            }
41            step++;
42        }
43        return -1;
44    }
45    
46    return result;
47};

Each of these solutions starts by first identifying the trees that should be cut. They do this by iterating over the cells in the 2D map, and adding any cell with a value greater than 1 to a separate data structure (a list in Python, an ArrayList in Java or C# or an array in JavaScript or C++). They then sort this list according to the tree heights.

After forming the sorted list (or array), the solutions find the shortest path from the current position to the next tree (starting from position (0,0)) by using Breadth-First Search (BFS). They maintain a queue that initially contains the starting position and a 2D visited array that keeps track of which cells they have already visited.

Starting from the current position, they iteratively dequeue a cell from the queue, and enqueue their non-visited neighbors that are not obstacles (cell with a value 1 or more). They simultaneously update the visited array, until they reach the next tree. If it isn't possible to reach the next tree, they return -1.

If they reach the next tree successfully, they add the distance to that tree to the total number of steps, and then they update the current position to be the tree's position. They continue this process until they have visited all the trees.

Finally, they return the total number of steps as the solution.

The time complexity of these solutions is O((mn)^2 log(mn)), where m is the number of rows and n is the number of columns in the forest 2D map. This is because in the worst case, they perform BFS (which takes O(mn) time) for each tree, and there are in most mn trees. The space complexity is O(m*n) due to the 2D visited array and queue in BFS.

These solutions can be further optimized by using A* Search Algorithm instead of BFS to find the shortest path from one tree to another, which could reduce the time complexity significantly for large inputs.