675. Cut Off Trees for Golf Event
Problem Description
You are asked to cut off trees in a forest for a golf event. The forest is represented as a non-negative 2D map, in this map:
- 0 represents the obstacle can't be reached.
- 1 represents the ground can be walked through.
- The place with number bigger than 1 represents a tree can be walked through, and this number represents the tree's height.
In one step you can walk in any of the four directions: north, east, south, west. If you are standing in a position with a tree, you can decide whether to cut off the tree.
You are asked to cut trees in a way that makes the forest have a height of 1 everywhere. You can start from any point with height bigger than 1 and perform the following operations:
- If you are standing in a position with a tree, cut off the tree.
- Move to any of the four directions.
Return the minimum number of steps you need to walk to cut off all the trees. If you cannot cut off all the trees, return -1.
Examples:
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.
Example 2:
Input: forest = [[1,2,3],[0,0,0],[7,6,5]] Output: -1 Explanation: The trees in the middle row cannot be accessed.
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
Python Solution
from collections import deque
from typing import List, Tuple
class Solution:
def cutOffTree(self, forest: List[List[int]]) -> int:
# Get all trees and sort by height
trees = []
for i in range(len(forest)):
for j in range(len(forest[0])):
if forest[i][j] > 1:
trees.append((forest[i][j], i, j))
trees.sort()
# Add starting point (0,0) if it's not a tree
if not trees or (trees[0][1] != 0 or trees[0][2] != 0):
trees.insert(0, (0, 0, 0))
def bfs(start: Tuple[int, int], end: Tuple[int, int]) -> int:
queue = deque([(start[0], start[1], 0)])
seen = {(start[0], start[1])}
while queue:
i, j, steps = queue.popleft()
if (i, j) == end:
return steps
for di, dj in [(0,1), (1,0), (0,-1), (-1,0)]:
ni, nj = i + di, j + dj
if (0 <= ni < len(forest) and
0 <= nj < len(forest[0]) and
forest[ni][nj] > 0 and
(ni, nj) not in seen):
seen.add((ni, nj))
queue.append((ni, nj, steps + 1))
return -1
# Calculate total steps
total_steps = 0
for i in range(len(trees) - 1):
steps = bfs((trees[i][1], trees[i][2]),
(trees[i+1][1], trees[i+1][2]))
if steps == -1:
return -1
total_steps += steps
return total_stepsImplementation Notes:
- Uses BFS to find shortest path between trees
- Time complexity: O(m²n² log(mn))
- Space complexity: O(mn)
- Sorts trees by height to ensure optimal cutting order
Java Solution
class Solution {
private static final int[][] dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}};
public int cutOffTree(List> forest) {
// Get all trees and sort by height
List trees = new ArrayList<>();
for (int i = 0; i < forest.size(); i++) {
for (int j = 0; j < forest.get(0).size(); j++) {
int height = forest.get(i).get(j);
if (height > 1) {
trees.add(new int[]{height, i, j});
}
}
}
Collections.sort(trees, (a, b) -> a[0] - b[0]);
// Add starting point if needed
if (trees.isEmpty() || trees.get(0)[1] != 0 || trees.get(0)[2] != 0) {
trees.add(0, new int[]{0, 0, 0});
}
int totalSteps = 0;
for (int i = 0; i < trees.size() - 1; i++) {
int steps = bfs(forest, trees.get(i), trees.get(i + 1));
if (steps == -1) return -1;
totalSteps += steps;
}
return totalSteps;
}
private int bfs(List> forest, int[] start, int[] end) {
int m = forest.size(), n = forest.get(0).size();
boolean[][] visited = new boolean[m][n];
Queue queue = new LinkedList<>();
queue.offer(new int[]{start[1], start[2], 0});
visited[start[1]][start[2]] = true;
while (!queue.isEmpty()) {
int[] curr = queue.poll();
if (curr[0] == end[1] && curr[1] == end[2]) {
return curr[2];
}
for (int[] dir : dirs) {
int ni = curr[0] + dir[0], nj = curr[1] + dir[1];
if (ni >= 0 && ni < m && nj >= 0 && nj < n &&
forest.get(ni).get(nj) > 0 && !visited[ni][nj]) {
visited[ni][nj] = true;
queue.offer(new int[]{ni, nj, curr[2] + 1});
}
}
}
return -1;
}
} C++ Solution
class Solution {
private:
const vector> dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}};
int bfs(const vector>& forest, const vector& start, const vector& end) {
int m = forest.size(), n = forest[0].size();
vector> visited(m, vector(n, false));
queue> q;
q.push({start[1], start[2], 0});
visited[start[1]][start[2]] = true;
while (!q.empty()) {
auto curr = q.front();
q.pop();
if (curr[0] == end[1] && curr[1] == end[2]) {
return curr[2];
}
for (const auto& dir : dirs) {
int ni = curr[0] + dir[0], nj = curr[1] + dir[1];
if (ni >= 0 && ni < m && nj >= 0 && nj < n &&
forest[ni][nj] > 0 && !visited[ni][nj]) {
visited[ni][nj] = true;
q.push({ni, nj, curr[2] + 1});
}
}
}
return -1;
}
public:
int cutOffTree(vector>& forest) {
// Get all trees and sort by height
vector> trees;
for (int i = 0; i < forest.size(); i++) {
for (int j = 0; j < forest[0].size(); j++) {
if (forest[i][j] > 1) {
trees.push_back({forest[i][j], i, j});
}
}
}
sort(trees.begin(), trees.end());
// Add starting point if needed
if (trees.empty() || trees[0][1] != 0 || trees[0][2] != 0) {
trees.insert(trees.begin(), {0, 0, 0});
}
int totalSteps = 0;
for (int i = 0; i < trees.size() - 1; i++) {
int steps = bfs(forest, trees[i], trees[i + 1]);
if (steps == -1) return -1;
totalSteps += steps;
}
return totalSteps;
}
}; JavaScript Solution
/**
* @param {number[][]} forest
* @return {number}
*/
var cutOffTree = function(forest) {
const dirs = [[0,1], [1,0], [0,-1], [-1,0]];
// Get all trees and sort by height
const trees = [];
for (let i = 0; i < forest.length; i++) {
for (let j = 0; j < forest[0].length; j++) {
if (forest[i][j] > 1) {
trees.push([forest[i][j], i, j]);
}
}
}
trees.sort((a, b) => a[0] - b[0]);
// Add starting point if needed
if (trees.length === 0 || trees[0][1] !== 0 || trees[0][2] !== 0) {
trees.unshift([0, 0, 0]);
}
function bfs(start, end) {
const m = forest.length, n = forest[0].length;
const visited = Array(m).fill().map(() => Array(n).fill(false));
const queue = [[start[1], start[2], 0]];
visited[start[1]][start[2]] = true;
while (queue.length > 0) {
const [i, j, steps] = queue.shift();
if (i === end[1] && j === end[2]) {
return steps;
}
for (const [di, dj] of dirs) {
const ni = i + di, nj = j + dj;
if (ni >= 0 && ni < m && nj >= 0 && nj < n &&
forest[ni][nj] > 0 && !visited[ni][nj]) {
visited[ni][nj] = true;
queue.push([ni, nj, steps + 1]);
}
}
}
return -1;
}
let totalSteps = 0;
for (let i = 0; i < trees.length - 1; i++) {
const steps = bfs(trees[i], trees[i + 1]);
if (steps === -1) return -1;
totalSteps += steps;
}
return totalSteps;
};C# Solution
public class Solution {
private readonly int[][] dirs = new int[][] {
new int[] {0,1}, new int[] {1,0},
new int[] {0,-1}, new int[] {-1,0}
};
public int CutOffTree(IList> forest) {
// Get all trees and sort by height
var trees = new List();
for (int i = 0; i < forest.Count; i++) {
for (int j = 0; j < forest[0].Count; j++) {
if (forest[i][j] > 1) {
trees.Add(new int[] {forest[i][j], i, j});
}
}
}
trees.Sort((a, b) => a[0].CompareTo(b[0]));
// Add starting point if needed
if (trees.Count == 0 || trees[0][1] != 0 || trees[0][2] != 0) {
trees.Insert(0, new int[] {0, 0, 0});
}
int totalSteps = 0;
for (int i = 0; i < trees.Count - 1; i++) {
int steps = Bfs(forest, trees[i], trees[i + 1]);
if (steps == -1) return -1;
totalSteps += steps;
}
return totalSteps;
}
private int Bfs(IList> forest, int[] start, int[] end) {
int m = forest.Count, n = forest[0].Count;
var visited = new bool[m, n];
var queue = new Queue<(int i, int j, int steps)>();
queue.Enqueue((start[1], start[2], 0));
visited[start[1], start[2]] = true;
while (queue.Count > 0) {
var (i, j, steps) = queue.Dequeue();
if (i == end[1] && j == end[2]) {
return steps;
}
foreach (var dir in dirs) {
int ni = i + dir[0], nj = j + dir[1];
if (ni >= 0 && ni < m && nj >= 0 && nj < n &&
forest[ni][nj] > 0 && !visited[ni, nj]) {
visited[ni, nj] = true;
queue.Enqueue((ni, nj, steps + 1));
}
}
}
return -1;
}
} Implementation Notes:
- Uses BFS to find shortest path between trees
- Time complexity: O(m²n² log(mn))
- Space complexity: O(mn)
- Handles edge cases like empty forest and unreachable trees