# Cut Off Trees for Golf Event
**Difficulty:** HARD
[External](https://leetcode.com/problems/cut-off-trees-for-golf-event)
Canonical: https://scaleengineer.com/dsa/problems/cut-off-trees-for-golf-event
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Heap (Priority Queue), Matrix
**Companies:** [Flipkart](https://scaleengineer.com/companies/flipkart)
---
## Problem
You are asked to cut off all the trees in a forest for a golf event. The forest is represented as an `m x n` matrix. In this matrix:

* `0` means the cell cannot be walked through.
* `1` represents an empty cell that can be walked through.
* A number greater than `1` represents a tree in a cell that can be walked through, and this number is the tree's height.

In one step, you can walk in any of the four directions: north, east, south, and west. If you are standing in a cell with a tree, you can choose whether to cut it off.

You must cut off the trees in order from shortest to tallest. When you cut off a tree, the value at its cell becomes `1` (an empty cell).

Starting from the point `(0, 0)`, return _the minimum steps you need to walk to cut off all the trees_. If you cannot cut off all the trees, return `-1`.

**Note:** The input is generated such that no two trees have the same height, and there is at least one tree needs to be cut off.

**Example 1:**

![](https://assets.glich.co/dsa/cut-off-trees-for-golf-event/image0.jpg) 

**Input:** forest = [[1,2,3],[0,0,4],[7,6,5]]
**Output:** 6
**Explanation:** Following the path above allows you to cut off the trees from shortest to tallest in 6 steps.

**Example 2:**

![](https://assets.glich.co/dsa/cut-off-trees-for-golf-event/image1.jpg) 

**Input:** forest = [[1,2,3],[0,0,0],[7,6,5]]
**Output:** -1
**Explanation:** The trees in the bottom row cannot be accessed as the middle row is blocked.

**Example 3:**

**Input:** forest = [[2,3,4],[0,0,5],[8,7,6]]
**Output:** 6
**Explanation:** You can follow the same path as Example 1 to cut off all the trees.
Note that you can cut off the first tree at (0, 0) before making any steps.

**Constraints:**

* `m == forest.length`
* `n == forest[i].length`
* `1 <= m, n <= 50`
* `0 <= forest[i][j] <= 109`
* Heights of all trees are **distinct**.

# Approaches
## Sorting Trees and Sequential BFS
This approach first identifies all the trees and sorts them by height, as required by the problem. Then, it calculates the minimum steps required to travel from the starting point `(0,0)` to the first tree, then from the first tree to the second, and so on, sequentially. The shortest path between any two points is found using a Breadth-First Search (BFS), which is ideal for finding the shortest path in an unweighted grid. The total steps are the sum of the steps for each segment of the journey.
**Time:** O(T * M * N), where `T` is the number of trees, and `M` and `N` are the dimensions of the forest. Finding and sorting trees takes O(M*N + T log T). We then perform `T` BFS traversals, and each BFS can take up to O(M * N) time in the worst case. The dominant term is O(T * M * N). · **Space:** O(M * N), where M and N are the dimensions of the forest. This space is used for the BFS queue and the `visited` matrix. The list of trees requires O(T) space, where T is the number of trees, but `T <= M*N`.
**Pros:** Conceptually straightforward and relatively easy to implement.; Guaranteed to find the shortest path for each segment because BFS is optimal for unweighted graphs.
**Cons:** Can be inefficient on large grids as BFS explores all reachable nodes within a certain distance, regardless of the direction of the target. This 'blind' search can explore many unnecessary cells.
### Explanation
The problem can be broken down into a series of shortest-path problems. Since we must cut trees in increasing order of height, the path is fixed: from `(0,0)` to the shortest tree, then to the second shortest, and so on. The main task is to calculate the distance for each leg of this journey.

1.  **Collect and Sort Trees:** We first traverse the entire grid to find all cells containing trees (value > 1). We store these trees' information—height, row, and column—in a list. Then, we sort this list based on tree height to get the mandatory cutting order.

2.  **Sequential Pathfinding with BFS:** We start at `(0,0)` and iterate through our sorted list of trees. For each tree, we need to find the minimum number of steps from our current location to that tree's location. Breadth-First Search (BFS) is the perfect algorithm for this, as it explores the grid layer by layer from a source, guaranteeing that the first time it reaches the destination, it does so via a shortest path. We run a separate BFS for each segment of the journey (e.g., from `(0,0)` to `tree1`, then `tree1` to `tree2`, etc.). If any BFS fails to find a path (meaning a tree is unreachable), we return -1. Otherwise, we sum up the steps from each successful BFS to get the total.

```java
import java.util.*;

class Solution {
    int[] dr = {-1, 1, 0, 0};
    int[] dc = {0, 0, -1, 1};

    public int cutOffTree(List<List<Integer>> forest) {
        int m = forest.size();
        int n = forest.get(0).size();

        List<int[]> trees = new ArrayList<>();
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (forest.get(r).get(c) > 1) {
                    trees.add(new int[]{forest.get(r).get(c), r, c});
                }
            }
        }

        Collections.sort(trees, (a, b) -> Integer.compare(a[0], b[0]));

        int totalSteps = 0;
        int startR = 0;
        int startC = 0;

        for (int[] tree : trees) {
            int endR = tree[1];
            int endC = tree[2];

            int steps = bfs(forest, startR, startC, endR, endC);

            if (steps == -1) {
                return -1;
            }
            totalSteps += steps;

            startR = endR;
            startC = endC;
        }
        return totalSteps;
    }

    private int bfs(List<List<Integer>> forest, int sr, int sc, int tr, int tc) {
        if (sr == tr && sc == tc) {
            return 0;
        }
        int m = forest.size();
        int n = forest.get(0).size();
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{sr, sc, 0}); // {row, col, steps}
        boolean[][] visited = new boolean[m][n];
        visited[sr][sc] = true;

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int r = curr[0];
            int c = curr[1];
            int steps = curr[2];

            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];

                if (nr >= 0 && nr < m && nc >= 0 && nc < n &&
                    !visited[nr][nc] && forest.get(nr).get(nc) != 0) {
                    
                    if (nr == tr && nc == tc) {
                        return steps + 1;
                    }
                    
                    visited[nr][nc] = true;
                    queue.offer(new int[]{nr, nc, steps + 1});
                }
            }
        }
        return -1;
    }
}
```
### Algorithm
- **Step 1: Collect and Sort Trees:**
  - Iterate through the `m x n` forest grid.
  - For each cell `(r, c)` with a value greater than 1, store it as a `(height, r, c)` tuple.
  - Collect all such tuples into a list.
  - Sort this list of trees in ascending order based on their height.
- **Step 2: Calculate Total Steps Sequentially:**
  - Initialize `total_steps = 0`.
  - Set the starting position `start = (0, 0)`.
  - Iterate through the sorted list of trees. For each `target` tree:
    - Perform a Breadth-First Search (BFS) to find the shortest path from `start` to `target`.
    - If the BFS cannot reach the `target`, it's impossible to cut all trees. Return -1.
    - If a path is found, add the number of steps to `total_steps`.
    - Update the `start` position to the current `target`'s coordinates for the next iteration.
- **Step 3: Return Result:**
  - After visiting all trees, return `total_steps`.

## Sorting Trees and Sequential A* Search
This approach is an optimization of the BFS-based solution. It follows the same high-level strategy of sorting the trees and calculating the path between them sequentially. However, instead of using BFS, it employs the A* (A-star) search algorithm for pathfinding. A* is an informed search algorithm that uses a heuristic to guide its search towards the target. This 'intelligent' search often explores far fewer cells than a 'blind' BFS, making it significantly faster on average, especially on larger or more open grids.
**Time:** Worst Case: O(T * M * N * log(M*N)). The `log(M*N)` factor comes from the priority queue operations. While this theoretical worst-case is higher than BFS's, A* is practically much faster on average because the heuristic prunes the search space significantly, leading to far fewer nodes being processed. · **Space:** O(M * N). The space is dominated by the `visited` matrix and the priority queue, which in the worst case could hold all `M*N` cells.
**Pros:** More efficient than BFS in practice for most grid-based pathfinding problems.; Reduces the number of explored cells by using a heuristic to intelligently guide the search towards the goal.
**Cons:** Slightly more complex to implement than BFS due to the priority queue and heuristic calculation.; The worst-case time complexity is theoretically higher than BFS due to the logarithmic factor of priority queue operations, although this is rarely a factor in practice with a good heuristic.
### Explanation
The core idea is to make the pathfinding step more efficient. While BFS is guaranteed to be optimal, it can be slow because it explores in all directions equally. A* improves upon this by using a heuristic to prioritize cells that are not only close to the start but also appear to be close to the destination.

- **A* Search Details:** A* works by maintaining a priority queue of cells to visit. The priority of a cell `n` is determined by the function `f(n) = g(n) + h(n)`.
  - `g(n)`: The known cost (number of steps) from the starting cell to cell `n`.
  - `h(n)`: A heuristic estimate of the cost from cell `n` to the target. For a grid, the **Manhattan distance** (`|row1 - row2| + |col1 - col2|`) is a perfect heuristic—it's fast to compute and never overestimates the actual cost (it's 'admissible'), which guarantees A* will find the shortest path.

By always exploring the cell with the lowest `f(n)` value, A* focuses its search in the direction of the target, pruning large parts of the search space that BFS would have needlessly explored.

```java
import java.util.*;

class Solution {
    int[] dr = {-1, 1, 0, 0};
    int[] dc = {0, 0, -1, 1};

    public int cutOffTree(List<List<Integer>> forest) {
        int m = forest.size();
        int n = forest.get(0).size();

        List<int[]> trees = new ArrayList<>();
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (forest.get(r).get(c) > 1) {
                    trees.add(new int[]{forest.get(r).get(c), r, c});
                }
            }
        }

        Collections.sort(trees, (a, b) -> Integer.compare(a[0], b[0]));

        int totalSteps = 0;
        int startR = 0;
        int startC = 0;

        for (int[] tree : trees) {
            int endR = tree[1];
            int endC = tree[2];

            int steps = aStar(forest, startR, startC, endR, endC);

            if (steps == -1) {
                return -1;
            }
            totalSteps += steps;

            startR = endR;
            startC = endC;
        }
        return totalSteps;
    }

    private int aStar(List<List<Integer>> forest, int sr, int sc, int tr, int tc) {
        if (sr == tr && sc == tc) {
            return 0;
        }
        int m = forest.size();
        int n = forest.get(0).size();
        
        // PriorityQueue stores {f_cost, g_cost, r, c}
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        
        int h_cost = Math.abs(sr - tr) + Math.abs(sc - tc);
        pq.offer(new int[]{h_cost, 0, sr, sc}); // f_cost, g_cost, r, c
        
        boolean[][] visited = new boolean[m][n];
        visited[sr][sc] = true;

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int g_cost = curr[1];
            int r = curr[2];
            int c = curr[3];

            if (r == tr && c == tc) {
                return g_cost;
            }

            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];

                if (nr >= 0 && nr < m && nc >= 0 && nc < n &&
                    !visited[nr][nc] && forest.get(nr).get(nc) != 0) {
                    
                    visited[nr][nc] = true;
                    int next_g_cost = g_cost + 1;
                    int next_h_cost = Math.abs(nr - tr) + Math.abs(nc - tc);
                    int next_f_cost = next_g_cost + next_h_cost;
                    pq.offer(new int[]{next_f_cost, next_g_cost, nr, nc});
                }
            }
        }
        return -1;
    }
}
```
### Algorithm
- **Step 1: Collect and Sort Trees:** This step is identical to the BFS approach. Find all trees, store them, and sort them by height.
- **Step 2: Calculate Total Steps with A* Search:**
  - Initialize `total_steps = 0` and `start = (0, 0)`.
  - Iterate through the sorted list of trees. For each `target` tree:
    - Perform an A* search to find the shortest path from `start` to `target`.
    - A* uses a priority queue to store nodes to visit. The priority is `f(n) = g(n) + h(n)`.
    - `g(n)` is the steps from the start to node `n`.
    - `h(n)` is the Manhattan distance from `n` to the target: `|n.row - target.row| + |n.col - target.col|`.
    - If A* cannot find a path, return -1.
    - Add the path cost (`g(n)` at the target) to `total_steps`.
    - Update `start` to the current `target`'s location.
- **Step 3: Return Result:**
  - After visiting all trees, return `total_steps`.

# Solutions
### Java

```java
class Solution {
private
  int[] dist = new int[3600];
private
  List<List<Integer>> forest;
private
  int m;
private
  int n;
public
  int cutOffTree(List<List<Integer>> forest) {
    this.forest = forest;
    m = forest.size();
    n = forest.get(0).size();
    List<int[]> trees = new ArrayList<>();
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (forest.get(i).get(j) > 1) {
          trees.add(new int[]{forest.get(i).get(j), i * n + j});
        }
      }
    }
    trees.sort(Comparator.comparingInt(a->a[0]));
    int ans = 0;
    int start = 0;
    for (int[] tree : trees) {
      int end = tree[1];
      int t = bfs(start, end);
      if (t == -1) {
        return -1;
      }
      ans += t;
      start = end;
    }
    return ans;
  }
private
  int bfs(int start, int end) {
    PriorityQueue<int[]> q =
        new PriorityQueue<>(Comparator.comparingInt(a->a[0]));
    q.offer(new int[]{f(start, end), start});
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[start] = 0;
    int[] dirs = {-1, 0, 1, 0, -1};
    while (!q.isEmpty()) {
      int state = q.poll()[1];
      if (state == end) {
        return dist[state];
      }
      for (int k = 0; k < 4; ++k) {
        int x = state / n + dirs[k];
        int y = state % n + dirs[k + 1];
        if (x >= 0 && x < m && y >= 0 && y < n && forest.get(x).get(y) > 0) {
          if (dist[x * n + y] > dist[state] + 1) {
            dist[x * n + y] = dist[state] + 1;
            q.offer(new int[]{dist[x * n + y] + f(x * n + y, end), x * n + y});
          }
        }
      }
    }
    return -1;
  }
private
  int f(int start, int end) {
    int a = start / n;
    int b = start % n;
    int c = end / n;
    int d = end % n;
    return Math.abs(a - c) + Math.abs(b - d);
  }
}

```

### CPP

```cpp
class Solution {
public:
  int m;
  int n;
  vector<int> dist;
  int cutOffTree(vector<vector<int>> &forest) {
    m = forest.size();
    n = forest[0].size();
    dist.resize(3600);
    vector<pair<int, int>> trees;
    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (forest[i][j] > 1)
          trees.push_back({forest[i][j], i * n + j});
    sort(trees.begin(), trees.end());
    int ans = 0;
    int start = 0;
    for (auto &tree : trees) {
      int end = tree.second;
      int t = bfs(start, end, forest);
      if (t == -1)
        return -1;
      ans += t;
      start = end;
    }
    return ans;
  }
  int bfs(int start, int end, vector<vector<int>> &forest) {
    priority_queue<pair<int, int>, vector<pair<int, int>>,
                   greater<pair<int, int>>>
        q;
    q.push({f(start, end), start});
    fill(dist.begin(), dist.end(), INT_MAX);
    dist[start] = 0;
    vector<int> dirs = {-1, 0, 1, 0, -1};
    while (!q.empty()) {
      int state = q.top().second;
      q.pop();
      if (state == end)
        return dist[state];
      for (int k = 0; k < 4; ++k) {
        int x = state / n + dirs[k], y = state % n + dirs[k + 1];
        if (x >= 0 && x < m && y >= 0 && y < n && forest[x][y] &&
            dist[x * n + y] > dist[state] + 1) {
          dist[x * n + y] = dist[state] + 1;
          q.push({dist[x * n + y] + f(x * n + y, end), x * n + y});
        }
      }
    }
    return -1;
  }
  int f(int start, int end) {
    int a = start / n, b = start % n;
    int c = end / n, d = end % n;
    return abs(a - c) + abs(b - d);
  }
};

```

### Python

```python
class Solution:
    def cutOffTree(self, forest: List[List[int]]) -> int: def f(i, j, x, y): return abs(i - x) + abs(j - y) def bfs(i, j, x, y): q = [(f(i, j, x, y), i, j)] dist = {i * n + j: 0} while q: _, i, j = heappop(q) step = dist[i * n + j] if (i, j) == (x, y): return step for a, b in [[0, - 1], [0, 1], [- 1, 0], [1, 0]]: c, d = i + a, j + b if 0 <= c < m and 0 <= d < n and forest[c][d] > 0: if c * n + d not in dist or dist[c * n + d] > step + 1: dist[c * n + d] = step + 1 heappush(q, (dist[c * n + d] + f(c, d, x, y), c, d)) return - 1 m, n = len(forest), len(forest[0]) trees = [(forest[i][j], i, j) for i in range(m) for j in range(n) if forest[i][j] > 1] trees . sort() i = j = 0 ans = 0 for _, x, y in trees: t = bfs(i, j, x, y) if t == - 1: return - 1 ans += t i, j = x, y return ans

```