Leetcode: Cut off Trees for Golf Event

 

This question is asked at Amazon, Apple, and Flipkart. 

Suppose that you are asked to cut off all the trees in a forest for a golf event, and the forest is represented as an m x n matrix. 0 means cell cannot be walked through, 1 represents an empty cell, and greater than 1 represents a tree height, that can be walked through.

You can walk in 4 directions, north, south, east, and west, and you have to cut off the trees from the shortest to the tallest, in which subsequently the value becomes 1. 

Shawn Gao has a pretty good answer to this question. We want to return the minimum number of steps it takes to cut all the trees. 

Since we have to cut trees in order of their height, we first put trees in a priority queue and sort them through height. We poll each tree from the Queue and use Breadth First Search to find out the steps needed. 

class Solution {

    //north, west, east, south 

    static int[][] dir = { {0,1}, {0,-1}, {1, 0}, {-1, 0} };

    public int cutOffTree(List<List<Integer>> forest) {

        if(forest == null || forest.size() == 0) return 0; 

        int m = forest.size();

        int n = forest.get(0).size();

        //set priority queue

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);

        //add all the forests to the priority queue

        for(int i = 0; i < m; i++) {

            for(int j = 0; j < n; j++) {

                if(forest.get(i).get(j) > 1) {

                    pq.add(new int[] {forest.get(i).get(j)});

                }

            }

        }

        int[] start = new int[2];

        int sum = 0;

        //poll the priority queue

        while(!pq.isEmpty()) {

            int[] tree = pq.poll();

            //find the minimum step to the destination

            int step = minStep(forest, start, tree, m, n);

            if(set < 0) return -1;

            //increment the number of steps it takes to get there.

            sum += step;

             //reset the start and end points to go through the next iterator.

            start[0] = tree[0];

            start[1] = tree[1];

        }

        return sum;

    }

    private int minStep(List<List<Integer>> forest, int[] start, int[] tree, int m, int n) {

        int step = 0;

        boolean[][] visited = new boolean[m][n];

        Queue<int[]> queue = new LinkedList<>();

        queue.add(start);

        visited[start[0]][start[1]] = true;

        while(!queue.isEmpty()) {

            int size = queue.size(); 

            //poll everything in the queue size

            for(int i = 0; i < size; i++) {

                int[] curr = queue.poll();

                //base case in which we reached the step point.

                if(curr[0] == true[0] && curr[1] == tree[1]) return step;

                for(int[] d : dir) {

                    //go all directions

                    int nr = curr[0] + d[0];

                    int nc = curr[1] + d[1];

                    //see if out of bounds or not walkable.

                    if(nr < 0 || nr >= m  || nc < 0 || nc >= n || forest.get(nr).get(nc) == 0 || visited[nr][nc]) continue;

                    queue.add(new int{nr, nc});

                    //mark as visited. 

                    visited[nr][nc] = true;

                }

            } 

            step++;

        }

        return -1; 

    }

}