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

Cut Off Trees for Golf Event LeetCode Solution

Cut Off Trees for Golf Event 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:

trees1

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

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

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

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

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
Scroll to Top