MANG Problem #43: Cut Off Trees for Golf Event (Hard)

1. Problem Statement

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 means the cell can be walked through.
> 1 means there is a tree in this cell that can be walked through, and the number is the tree's height.

You must cut off the trees in order from shortest to tallest. When you cut a tree, its value becomes 1.

Return the minimum steps required to cut off all trees. If you can't, return -1.

2. Approach: Sorting + BFS

This problem combines Sorting and Shortest Path (BFS). We must travel between specific points in a specific order.

Extract and Sort: Scan the grid to find all trees (value > 1). Store their coordinates and heights in a list. Sort the list by height.
Point-to-Point BFS: The total steps are the sum of shortest paths from Start -> Tree1, Tree1 -> Tree2, etc.
BFS Function: Write a helper function bfs(startR, startC, targetR, targetC) that returns the minimum steps to reach the target, treating 0s as walls.
Execute: Iterate through the sorted list, running BFS between consecutive points. If any BFS returns -1, the whole sequence is impossible.

3. Java Implementation

public int cutOffTree(List<List<Integer>> forest) {
    if (forest == null || forest.size() == 0) return 0;
    int m = forest.size(), n = forest.get(0).size();
    
    // 1. Extract and sort trees
    List<int[]> trees = new ArrayList<>();
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            int v = forest.get(r).get(c);
            if (v > 1) trees.add(new int[]{v, r, c});
        }
    }
    trees.sort((a, b) -> Integer.compare(a[0], b[0]));
    
    // 2. BFS from point to point
    int totalSteps = 0;
    int sr = 0, sc = 0; // Starting point
    
    for (int[] tree : trees) {
        int steps = bfs(forest, sr, sc, tree[1], tree[2]);
        if (steps == -1) return -1;
        totalSteps += steps;
        sr = tree[1];
        sc = tree[2];
    }
    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(), n = forest.get(0).size();
    Queue<int[]> q = new LinkedList<>();
    boolean[][] visited = new boolean[m][n];
    
    q.offer(new int[]{sr, sc});
    visited[sr][sc] = true;
    int steps = 0;
    int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};
    
    while (!q.isEmpty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            int[] curr = q.poll();
            if (curr[0] == tr && curr[1] == tc) return steps;
            
            for (int[] d : dirs) {
                int nr = curr[0] + d[0], nc = curr[1] + d[1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && 
                    !visited[nr][nc] && forest.get(nr).get(nc) > 0) {
                    visited[nr][nc] = true;
                    q.offer(new int[]{nr, nc});
                }
            }
        }
        steps++;
    }
    return -1;
}

4. 5-Minute "Video-Style" Walkthrough

The Breakdown: The problem sounds complex, but it's just multiple smaller, independent problems. We have $K$ trees. We need to do $K$ separate BFS traversals.
The Obstacles: The trees that are not your current target act exactly like empty ground (1). You can walk right over them. You only get blocked by 0.
The State Reset: Notice that the visited array inside the bfs helper is newly created for every search. We must clear our memory of where we've been because a cell that was a dead-end on the way to Tree 1 might be the only path to Tree 2.

5. Interview Discussion