Skip to content
LeetCode 675: Cut Off Trees with BFS, A* Search, and Union-Find Optimizations
Fundamentals 21 min read

LeetCode 675: Cut Off Trees with BFS, A* Search, and Union-Find Optimizations

This article provides a comprehensive solution to LeetCode 675 'Cut Off Trees for Golf Event', detailing BFS, A* heuristic search, and Union-Find pre-processing for unreachable cases, with full Java implementations and complexity analysis.

Java Tech Enthusiast
Java Tech Enthusiast
Java Tech Enthusiast

Problem Description

LeetCode 675: You are asked to cut off trees in a forest represented by an m x n matrix. Each cell can be: 0 – obstacle, cannot be entered. 1 – ground, walkable. >1 – a tree with height equal to the cell value; walkable and can be cut (becomes ground).

Starting at (0,0), you must cut trees in increasing order of height. Move in four directions; each step costs 1. Return the minimum total steps to cut all trees, or -1 if impossible. All tree heights are distinct, and at least one tree exists.

Basic Analysis

The cutting order is uniquely determined by sorting all tree cells by height. A key property: cutting a tree only changes its cell to ground ( 1), never to an obstacle, so shortest paths between any two points never become longer as the process proceeds. Therefore, the total minimum steps equals the sum of shortest-path distances between consecutive trees in the sorted order (including from (0,0) to the first tree).

BFS Solution

Because the grid size is at most 50x50 and edge weights are uniform (1), BFS is suitable for each pairwise shortest path.

Algorithm:

Scan the grid, collect all tree cells as tuples (height, x, y).

Sort the list by height ascending.

If the start cell (0,0) is an obstacle ( 0), return -1.

For each consecutive pair (including start to first tree), run BFS to compute the shortest distance. If any BFS returns -1, the whole task is impossible.

Accumulate distances.

Complexity: Let K be the number of trees ( K ≤ 2500). Preprocessing O(mn), sorting O(K log K). Each BFS is O(mn), run K times → O(K·mn). With mn ≤ 2500, worst-case operations ~6.25 million, well within limits.

class Solution { int N = 50; int[][] g = new int[N][N]; int n, m; List<int[]> list = new ArrayList<>(); public int cutOffTree(List<List<Integer>> forest) { n = forest.size(); m = forest.get(0).size(); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { g[i][j] = forest.get(i).get(j); if (g[i][j] > 1) list.add(new int[]{g[i][j], i, j}); } } Collections.sort(list, (a,b)->a[0]-b[0]); if (g[0][0] == 0) return -1; int x = 0, y = 0, ans = 0; for (int[] ne : list) { int nx = ne[1], ny = ne[2]; int d = bfs(x, y, nx, ny); if (d == -1) return -1; ans += d; x = nx; y = ny; } return ans; } int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}}; int bfs(int X, int Y, int P, int Q) { if (X == P && Y == Q) return 0; boolean[][] vis = new boolean[n][m]; Deque<int[]> d = new ArrayDeque<>(); d.addLast(new int[]{X, Y}); vis[X][Y] = true; int ans = 0; while (!d.isEmpty()) { int size = d.size(); while (size-- > 0) { int[] info = d.pollFirst(); int x = info[0], y = info[1]; for (int[] di : dirs) { int nx = x + di[0], ny = y + di[1]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if (g[nx][ny] == 0 || vis[nx][ny]) continue; if (nx == P && ny == Q) return ans + 1; d.addLast(new int[]{nx, ny}); vis[nx][ny] = true; } } ans++; } return -1; } }

A* Algorithm

BFS explores uniformly in all directions. A* uses a heuristic to prioritize moves toward the target. For a grid with uniform cost, the Manhattan distance |x1-x2| + |y1-y2| is an admissible heuristic (never overestimates the true cost).

Algorithm:

State: (estimated_total_cost, x, y) where

estimated_total_cost = steps_so_far + manhattan(x, y, target_x, target_y)

.

Use a priority queue (min-heap) ordered by estimated_total_cost.

Maintain a map best_steps[idx] recording the smallest actual steps found to reach each cell.

When popping a state, if its recorded steps are outdated (larger than best_steps), skip it.

For each neighbor, if it's the target, return steps_so_far + 1. Otherwise, if the neighbor is not an obstacle and either not visited or we found a shorter path to it ( best_steps[neighbor] > steps_so_far + 1), update best_steps and push the neighbor with its new estimated total cost.

Correctness Note: The heuristic guarantees that the first time we pop the target, we have the optimal path. However, for intermediate nodes, a later relaxation may find a shorter actual path, so we must allow re-insertion when best_steps[neighbor] > steps_so_far + 1.

class Solution { int N = 50; int[][] g = new int[N][N]; int n, m; List<int[]> list = new ArrayList<>(); public int cutOffTree(List<List<Integer>> forest) { n = forest.size(); m = forest.get(0).size(); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { g[i][j] = forest.get(i).get(j); if (g[i][j] > 1) list.add(new int[]{g[i][j], i, j}); } } if (g[0][0] == 0) return -1; Collections.sort(list, (a,b)->a[0]-b[0]); int x = 0, y = 0, ans = 0; for (int[] ne : list) { int nx = ne[1], ny = ne[2]; int d = astar(x, y, nx, ny); if (d == -1) return -1; ans += d; x = nx; y = ny; } return ans; } int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}}; int getIdx(int x, int y) { return x * m + y; } int f(int X, int Y, int P, int Q) { return Math.abs(X - P) + Math.abs(Y - Q); } int astar(int X, int Y, int P, int Q) { if (X == P && Y == Q) return 0; Map<Integer, Integer> map = new HashMap<>(); PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->a[0]-b[0]); q.add(new int[]{f(X, Y, P, Q), X, Y}); map.put(getIdx(X, Y), 0); while (!q.isEmpty()) { int[] info = q.poll(); int x = info[1], y = info[2], step = map.get(getIdx(x, y)); for (int[] di : dirs) { int nx = x + di[0], ny = y + di[1], nidx = getIdx(nx, ny); if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if (g[nx][ny] == 0) continue; if (nx == P && ny == Q) return step + 1; if (!map.containsKey(nidx) || map.get(nidx) > step + 1) { q.add(new int[]{step + 1 + f(nx, ny, P, Q), nx, ny}); map.put(nidx, step + 1); } } } return -1; } }

A* with Union-Find Preprocessing for Unreachable Cases

When obstacles force the optimal path to go opposite to the heuristic direction, A* may explore many extra nodes due to the priority queue overhead. A cheap pre-check can eliminate impossible cases early: use Union-Find to verify that every tree is connected to (0,0) through non-obstacle cells.

Algorithm:

During the initial grid scan, initialize a Union-Find structure over all m*n cells.

For each non-obstacle cell, union it with its left and up neighbors (if they are also non-obstacle). This builds connected components in O(mn α(mn)) time.

After collecting and sorting trees, check if each tree's component matches (0,0) 's component. If any tree is disconnected, return -1 immediately.

Proceed with A* for the remaining pairwise distances.

This adds negligible overhead but avoids fruitless A* searches on impossible instances.

class Solution { int N = 50; int[][] g = new int[N][N]; int n, m; int[] p = new int[N * N + 10]; List<int[]> list = new ArrayList<>(); void union(int a, int b) { p[find(a)] = p[find(b)]; } boolean query(int a, int b) { return find(a) == find(b); } int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } int getIdx(int x, int y) { return x * m + y; } public int cutOffTree(List<List<Integer>> forest) { n = forest.size(); m = forest.get(0).size(); for (int i = 0; i < n * m; i++) p[i] = i; int[][] tempDirs = {{0,-1},{-1,0}}; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { g[i][j] = forest.get(i).get(j); if (g[i][j] > 1) list.add(new int[]{g[i][j], i, j}); if (g[i][j] == 0) continue; for (int[] di : tempDirs) { int nx = i + di[0], ny = j + di[1]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if (g[nx][ny] != 0) union(getIdx(i, j), getIdx(nx, ny)); } } } for (int[] info : list) { int x = info[1], y = info[2]; if (!query(getIdx(0,0), getIdx(x, y))) return -1; } Collections.sort(list, (a,b)->a[0]-b[0]); int x = 0, y = 0, ans = 0; for (int[] ne : list) { int nx = ne[1], ny = ne[2]; int d = astar(x, y, nx, ny); if (d == -1) return -1; ans += d; x = nx; y = ny; } return ans; } int f(int X, int Y, int P, int Q) { return Math.abs(X - P) + Math.abs(Y - Q); } int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}}; int astar(int X, int Y, int P, int Q) { if (X == P && Y == Q) return 0; Map<Integer, Integer> map = new HashMap<>(); PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->a[0]-b[0]); q.add(new int[]{f(X, Y, P, Q), X, Y}); map.put(getIdx(X, Y), 0); while (!q.isEmpty()) { int[] info = q.poll(); int x = info[1], y = info[2], step = map.get(getIdx(x, y)); for (int[] di : dirs) { int nx = x + di[0], ny = y + di[1], nidx = getIdx(nx, ny); if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if (g[nx][ny] == 0) continue; if (nx == P && ny == Q) return step + 1; if (!map.containsKey(nidx) || map.get(nidx) > step + 1) { q.add(new int[]{step + 1 + f(nx, ny, P, Q), nx, ny}); map.put(nidx, step + 1); } } } return -1; } }
Original Source

Signed-in readers can open the original source through BestHub's protected redirect.

Sign in to view source
Republication Notice

This article has been distilled and summarized from source material, then republished for learning and reference. If you believe it infringes your rights, please contactadmin@besthub.devand we will review it promptly.

JavaAlgorithmBFSA* SearchUnion-FindShortest PathLeetCode 675Matrix Traversal
Reader feedback

How this landed with the community

Sign in to like

Rate this article

Was this worth your time?

Sign in to rate
Discussion

0 Comments

Thoughtful readers leave field notes, pushback, and hard-won operational detail here.