675. Cut Off Trees for Golf Event

/**

 * 675. Cut Off Trees for Golf Event

 * 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.

 *

 * You are guaranteed that no two trees have the same height, and there is at least one tree needs to be cut off.

 * Example 1:

 * 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.

 */

Here is the solution at github: https://github.com/zcoderz/leetcode/blob/main/src/main/java/frequent/hard/GolfCutOff.java

Observation: Need to cut all trees in increasing order of height and return the minimum distance travelled to cut all trees. Problem can be broken down into two parts:

1. Sort trees by their height
2. Iterate over the trees
   1. Find minimum distance from previous location to the next tree
   1. This can be solved via a simple BFS
   1. If path to tree doesn’t exist return -1

Here is the code:

public int cutOffTree(List<List<Integer>> forest) {
    List<int[]> trees = new ArrayList();
    for (int r = 0; r < forest.size(); ++r) {
        for (int c = 0; c < forest.get(0).size(); ++c) {
            int v = forest.get(r).get(c);
            if (v > 1) trees.add(new int[]{v, r, c});
        }
    }

    Collections.sort(trees, Comparator.comparingInt(a -> a[0]));

    int ans = 0, sr = 0, sc = 0;
    for (int[] tree: trees) {
        int d = dist(forest, sr, sc, tree[1], tree[2]);
        if (d < 0) return -1;
        ans += d;
        sr = tree[1]; sc = tree[2];
    }
    return ans;
}

public int dist(List<List<Integer>> forest, int sr, int sc, int tr, int tc) {
    int R = forest.size(), C = forest.get(0).size();
    Queue<int[]> queue = new LinkedList();
    queue.add(new int[]{sr, sc, 0});
    boolean[][] seen = new boolean[R][C];
    seen[sr][sc] = true;
    while (!queue.isEmpty()) {
        int[] cur = queue.poll();
        if (cur[0] == tr && cur[1] == tc) return cur[2];
        for (int di = 0; di < 4; ++di) {
            int r = cur[0] + dr[di];
            int c = cur[1] + dc[di];
            if (0 <= r && r < R && 0 <= c && c < C &&
                    !seen[r][c] && forest.get(r).get(c) > 0) {
                seen[r][c] = true;
                queue.add(new int[]{r, c, cur[2]+1});
            }
        }
    }
    return -1;
}