Last updated on July 21st, 2024 at 03:43 am
Here, We see Cut Off Trees for Golf Event LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
Topics
Breadth-First Search
Companies
Amazon
Level of Question
Hard
![Cut Off Trees for Golf Event LeetCode Solution](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2024/02/LeetCode-Problem-Solution.png?resize=200%2C200&ssl=1)
Cut Off Trees for Golf Event LeetCode Solution
Table of Contents
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
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
.
Note: The input is generated such that no two trees have the same height, and there is at least one tree needs to be cut off.
Example 1:
![trees1](https://i0.wp.com/assets.leetcode.com/uploads/2020/11/26/trees1.jpg?w=1400&ssl=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:
![trees2](https://i0.wp.com/assets.leetcode.com/uploads/2020/11/26/trees2.jpg?w=1400&ssl=1)
Input: forest = [[1,2,3],[0,0,0],[7,6,5]]
Output: -1
Explanation: The trees in the bottom row cannot be accessed as the middle row is blocked.
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.
1. Cut Off Trees for Golf Event LeetCode Solution C++
class Solution { static constexpr int DIR[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; struct Cell { short r : 8; short c : 8; }; int doit(const vector<vector<int>>& forest, Cell start, vector<int> &curr, vector<int> &prev, vector<Cell> &bfs) { const int M = forest.size(), N = forest[0].size(); int steps = 0; swap(curr, prev); fill(begin(curr), end(curr), -1); curr[start.r * N + start.c] = steps; if (prev[start.r * N + start.c] != -1) { return prev[start.r * N + start.c]; } bfs.clear(); bfs.push_back(start); while (!bfs.empty()) { int size = bfs.size(); steps++; while (size--) { auto [r0, c0] = bfs[size]; swap(bfs[size], bfs.back()); bfs.pop_back(); for (auto [dr, dc] : DIR) { short r1 = r0 + dr, c1 = c0 + dc; int pos = r1 * N + c1; if (r1 >= 0 && r1 < M && c1 >= 0 && c1 < N && forest[r1][c1] > 0 && curr[pos] == -1) { if (prev[pos] != -1) { return steps + prev[pos]; } curr[pos] = steps; bfs.push_back({r1, c1}); } } } } return -1; } int manhattan_distance(vector<Cell> &cells) { int result = 0; Cell prev{0, 0}; for (auto &cell : cells) { result += abs(prev.r - cell.r) + abs(prev.c - cell.c); prev = cell; } return result; } public: int cutOffTree(vector<vector<int>>& forest) { const int M = forest.size(), N = forest[0].size(); if (forest[0][0] == 0) { return -1; } int obstacles = 0; vector<Cell> cells; cells.reserve(8); for (short r = 0; r < M; r++) { for (short c = 0; c < N; c++) { if (forest[r][c] > 1) { cells.push_back({r, c}); } else if (forest[r][c] == 0) { obstacles++; } } } sort(begin(cells), end(cells), [&forest](const Cell &a, const Cell &b){ return forest[a.r][a.c] < forest[b.r][b.c]; }); if (obstacles == 0) { return manhattan_distance(cells); } vector<int> curr(M * N, -1), prev = curr; curr[0] = 0; vector<Cell> bfs; bfs.reserve(8); int steps = 0; for (auto &cell : cells) { int result = doit(forest, cell, curr, prev, bfs); if (result != -1) { steps += result; } else { return -1; } } return steps; } };
2. Cut Off Trees for Golf Event LeetCode Solution Java
class Solution { public int cutOffTree(List<List<Integer>> forest) { PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->(forest.get(a[0]).get(a[1])-forest.get(b[0]).get(b[1]))); for(int i=0;i<forest.size();i++){ for(int j=0;j<forest.get(0).size();j++){ if(forest.get(i).get(j)>1) pq.add(new int[]{i,j}); } } int ans=0; int curr[]={0,0}; while(pq.size()>0){ int[] temp=pq.poll(); int dis=calcDis(forest,curr,temp); if(dis==-1) return -1; ans+=dis; curr=temp; } return ans; } int calcDis(List<List<Integer>> forest,int start[],int end[]){ int n=forest.size(),m=forest.get(0).size(); boolean vis[][]=new boolean[n][m]; Queue<int[]> queue=new LinkedList<>(); queue.add(start); vis[start[0]][start[1]]=true; int dis=0; while(queue.size()>0){ int len =queue.size(); while(len-->0){ int temp[]=queue.remove(); int r=temp[0],c=temp[1]; if(r==end[0] && c==end[1]) return dis; if(r+1<n && !vis[r+1][c] && forest.get(r+1).get(c)!=0){ queue.add(new int[]{r+1,c}); vis[r+1][c]=true; }if(r-1>=0 && !vis[r-1][c] && forest.get(r-1).get(c)!=0){ queue.add(new int[]{r-1,c}); vis[r-1][c]=true; }if(c-1>=0 && !vis[r][c-1] && forest.get(r).get(c-1)!=0){ queue.add(new int[]{r,c-1}); vis[r][c-1]=true; }if(c+1<m && !vis[r][c+1] && forest.get(r).get(c+1)!=0){ queue.add(new int[]{r,c+1}); vis[r][c+1]=true; } } dis++; } return -1; } }
3. Cut Off Trees for Golf Event LeetCode Solution JavaScript
var cutOffTree = function (forest) { let trees = forest.flat().filter(x => x && x !== 1).sort((a, b) => b - a); let currPos = [0, 0], totalDist = 0; while (trees.length) { let grid = [...forest.map(row => [...row])]; let ans = getDist(currPos, trees.pop(), grid); if (ans == null) return -1; let [pos, dist] = ans; currPos = pos; totalDist += dist; } return totalDist; function getDist(start, target, grid) { let dir = [[1, 0], [-1, 0], [0, 1], [0, -1]]; let queue = [start], dist = 0; while (queue.length) { let next = []; for (let [r, c] of queue) { if (grid[r][c] === target) return [[r, c], dist]; if (!grid[r][c]) continue; for (let [x, y] of dir) { x += r; y += c; if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length && grid[x][y]) next.push([x, y]) } grid[r][c] = 0; } dist++; queue = next; } return null; } };
4. Cut Off Trees for Golf Event LeetCode Solution Python
class Solution(object): def cutOffTree(self, forest): # 1. use min heap to sort the tree by height heap = [] for r in range(len(forest)): for c in range(len(forest[0])): if forest[r][c] > 1: heapq.heappush(heap, (forest[r][c], r, c)) totalSteps, currR, currC = 0, 0, 0 while heap: height, r, c = heapq.heappop(heap) steps = self.bfsGetMinSteps(forest, currR, currC, r, c) if steps == -1: return -1 currR, currC = r, c totalSteps += steps return totalSteps def bfsGetMinSteps(self, forest, currR, currC, targetR, targetC): directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] m, n = len(forest), len(forest[0]) q = collections.deque([(currR, currC)]) visited = set([(currR, currC)]) steps = 0 while q: sameLevelCounts = len(q) for _ in range(sameLevelCounts): r, c = q.popleft() if r == targetR and c == targetC: return steps for dr, dc in directions: nextR, nextC = r + dr, c + dc if 0 <= nextR < m and 0 <= nextC < n and (nextR, nextC) not in visited and forest[nextR][nextC] != 0: visited.add((nextR, nextC)) q.append((nextR, nextC)) steps += 1 return -1