# Cut Off Trees for Golf Event LeetCode Solution

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

## 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:

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

## Cut Off Trees for Golf Event LeetCode SolutionC++

``````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;
}
};```Code language: PHP (php)```

## Cut Off Trees for Golf Event LeetCode SolutionJava

``````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)
}
}
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];
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){
vis[r+1][c]=true;
}if(r-1>=0 && !vis[r-1][c] && forest.get(r-1).get(c)!=0){
vis[r-1][c]=true;
}if(c-1>=0 && !vis[r][c-1] && forest.get(r).get(c-1)!=0){
vis[r][c-1]=true;
}if(c+1<m && !vis[r][c+1] && forest.get(r).get(c+1)!=0){
vis[r][c+1]=true;
}
}
dis++;
}
return -1;
}
}```Code language: PHP (php)```

## Cut Off Trees for Golf Event LeetCode SolutionJavaScript

``````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;
}

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;
}
};```Code language: JavaScript (javascript)```

## Cut Off Trees for Golf Event LeetCode SolutionPython

``````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

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: