Cut Off Trees for Golf Event

hard bfs heap

Problem

Cut trees in ascending height order, starting at (0,0). Return total min steps or -1 if unreachable.

Inputforest=[[1,2,3],[0,0,4],[7,6,5]]

Output6

Visit each tree by height.

input

def cut_off_tree(forest):
    from collections import deque
    m, n = len(forest), len(forest[0])
    trees = sorted((forest[r][c], r, c) for r in range(m) for c in range(n) if forest[r][c] > 1)
    def bfs(sr, sc, tr, tc):
        if (sr, sc) == (tr, tc): return 0
        seen = {(sr, sc)}; q = deque([(sr, sc, 0)])
        while q:
            r, c, d = q.popleft()
            for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
                rr, cc = r + dr, c + dc
                if 0 <= rr < m and 0 <= cc < n and forest[rr][cc] != 0 and (rr, cc) not in seen:
                    if (rr, cc) == (tr, tc): return d + 1
                    seen.add((rr, cc)); q.append((rr, cc, d + 1))
        return -1
    total = 0; r, c = 0, 0
    for _, tr, tc in trees:
        d = bfs(r, c, tr, tc)
        if d == -1: return -1
        total += d; r, c = tr, tc
    return total

function cutOffTree(forest) {
  const m = forest.length, n = forest[0].length;
  const trees = [];
  for (let r = 0; r < m; r++) for (let c = 0; c < n; c++) if (forest[r][c] > 1) trees.push([forest[r][c], r, c]);
  trees.sort((a, b) => a[0] - b[0]);
  const bfs = (sr, sc, tr, tc) => {
    if (sr === tr && sc === tc) return 0;
    const seen = new Set([sr + ',' + sc]); const q = [[sr, sc, 0]];
    while (q.length) {
      const [r, c, d] = q.shift();
      for (const [dr, dc] of [[1,0],[-1,0],[0,1],[0,-1]]) {
        const rr = r + dr, cc = c + dc;
        if (rr >= 0 && rr < m && cc >= 0 && cc < n && forest[rr][cc] !== 0 && !seen.has(rr + ',' + cc)) {
          if (rr === tr && cc === tc) return d + 1;
          seen.add(rr + ',' + cc); q.push([rr, cc, d + 1]);
        }
      }
    }
    return -1;
  };
  let total = 0, r = 0, c = 0;
  for (const [, tr, tc] of trees) {
    const d = bfs(r, c, tr, tc); if (d === -1) return -1;
    total += d; r = tr; c = tc;
  }
  return total;
}

int cutOffTree(List> forest) {
    int m = forest.size(), n = forest.get(0).size();
    List 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});
    trees.sort((a, b) -> a[0] - b[0]);
    int total = 0, R = 0, C = 0;
    for (int[] t : trees) {
        int d = bfs(forest, R, C, t[1], t[2], m, n);
        if (d == -1) return -1;
        total += d; R = t[1]; C = t[2];
    }
    return total;
}
int bfs(List> f, int sr, int sc, int tr, int tc, int m, int n) {
    if (sr == tr && sc == tc) return 0;
    boolean[][] seen = new boolean[m][n]; seen[sr][sc] = true;
    Deque q = new ArrayDeque<>(); q.add(new int[]{sr, sc, 0});
    int[][] D = {{1,0},{-1,0},{0,1},{0,-1}};
    while (!q.isEmpty()) {
        int[] cur = q.poll();
        for (int[] d : D) {
            int rr = cur[0] + d[0], cc = cur[1] + d[1];
            if (rr < 0 || rr >= m || cc < 0 || cc >= n || f.get(rr).get(cc) == 0 || seen[rr][cc]) continue;
            if (rr == tr && cc == tc) return cur[2] + 1;
            seen[rr][cc] = true; q.add(new int[]{rr, cc, cur[2] + 1});
        }
    }
    return -1;
}

int bfs(vector>& f, int sr, int sc, int tr, int tc) {
    if (sr == tr && sc == tc) return 0;
    int m = f.size(), n = f[0].size();
    vector> seen(m, vector(n)); seen[sr][sc] = true;
    queue> q; q.push({sr, sc, 0});
    int D[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
    while (!q.empty()) {
        auto [r, c, d] = q.front(); q.pop();
        for (auto& dr : D) {
            int rr = r + dr[0], cc = c + dr[1];
            if (rr < 0 || rr >= m || cc < 0 || cc >= n || f[rr][cc] == 0 || seen[rr][cc]) continue;
            if (rr == tr && cc == tc) return d + 1;
            seen[rr][cc] = true; q.push({rr, cc, d + 1});
        }
    }
    return -1;
}
int cutOffTree(vector>& forest) {
    int m = forest.size(), n = forest[0].size();
    vector> trees;
    for (int r = 0; r < m; r++) for (int c = 0; c < n; c++) if (forest[r][c] > 1) trees.push_back({forest[r][c], r, c});
    sort(trees.begin(), trees.end());
    int total = 0, R = 0, C = 0;
    for (auto& [_, tr, tc] : trees) {
        int d = bfs(forest, R, C, tr, tc); if (d == -1) return -1;
        total += d; R = tr; C = tc;
    }
    return total;
}

Explanation

You must cut the trees in strictly increasing height order, always walking from your current spot to the next-shortest tree. The total cost is just the sum of the shortest walking distances between consecutive trees.

Step one: collect every cell with a tree (value > 1) and sort them by height. That fixes the visiting order — no choice is involved, you can only cut the shortest remaining tree next.

Step two: for each consecutive pair, run a BFS (breadth-first search) from your current position to the target tree. On a grid where every move costs 1, BFS finds the shortest path in steps, skipping blocked cells (value 0).

We add up each BFS distance into total. If any BFS can't reach the next tree, the whole task is impossible and we return -1.

Example: forest = [[1,2,3],[0,0,4],[7,6,5]]. Visiting heights 2, 3, 4, 5, 6, 7 in order and summing the BFS hops gives a total of 6. With T trees on an m×n grid, this is O(m·n·T).

Time: O(m·n·T) Space: O(m·n)