Cut Off Trees for Golf Event

This page explains Java solution to problem Cut Off Trees for Golf Event using Hadlock algorithm.

Problem Statement

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 positive number represents the tree's height.

In one step you can walk in any of the four directions top, bottom, left and right also when standing in a point which is a tree you can decide whether or not to cut off the tree.

You are asked to cut off all the trees in this forest in the order of tree's height - always cut off the tree with lowest height first. And after cutting, the original place has the tree will become a grass (value 1).

You will start from the point (0, 0) and you should output the minimum steps you need to walk to cut off all the trees. If you can't cut off all the trees, output -1 in that situation.

You are guaranteed that no two trees have the same height and there is at least one tree needs to be cut off.

Input:
[
[1,2,3],
[0,0,4],
[7,6,5]
]
Output: 6

Input:
[
[1,2,3],
[0,0,0],
[7,6,5]
]
Output: -1

Input:
[
[2,3,4],
[0,0,5],
[8,7,6]
]
Output: 6

Solution

package com.vc.hard;

import java.util.*;

class CutOffTreesForGolfEvent {
    public int cutOffTree(List<List<Integer>> forest) {
        if(forest == null) return 0;

        int n = forest.size();
        if(n == 0) return 0;
        int m = forest.get(0).size();

        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>(){
            public int compare(int[] e1, int[] e2) {
                return Integer.compare(e1[2], e2[2]);
            }
        });

        for(int i = 0; i < forest.size(); i++) {
            for(int j = 0; j < forest.get(i).size(); j++) {
                int val = forest.get(i).get(j);
                if(val >= 1) {
                    pq.offer(new int[]{i, j, val});
                }
            }
        }

        int res = 0;
        int[] prev = new int[]{0, 0, forest.get(0).get(0)};
        while(!pq.isEmpty()) {
            int[] current = pq.poll();
            int distance = getDistance(forest, prev, current, n, m);
            if(distance == -1) return -1;
            res += distance;
            prev = current;
            forest.get(current[0]).set(current[1], 1);
        }
        return res;
    }

    private int[][] dirs = {{1, 0},{0, 1},{-1, 0},{0, -1}};
    private int getDistance(List<List<Integer>> forest,
                            int[] source, int[] target, int totalRow, int totalCol) {
        //Hadlock's Algorithm
        Deque<int[]> q = new ArrayDeque<>();
        q.offerFirst(new int[]{source[0], source[1], 0});
        HashSet<String> visited = new HashSet<>();

        /**
             Hadlock Algorithm works on detour,
             if move takes us away from target, then we increment detour
             else we don't increment detour

             Final distance from source to target will be
             distance = (target[0] - source[0]) + (target[1] - source[1]) + 2 * detour;

             2 * detour because we have to cover detour two times,
             Once when we go away from target
             And then back to target again.
         */
        while(!q.isEmpty()) {
            int[] e = q.pollFirst();

            if(e[0] == target[0] && e[1] == target[1]) {
                return Math.abs(target[0] - source[0]) + Math.abs(target[1] - source[1]) + 2 * e[2];
            }
            String key = e[0] + " " + e[1];

            if(visited.contains(key)) continue;

            visited.add(key);
            for(int[] dir: dirs) {
                int eNewX = e[0] + dir[0];
                int eNewY = e[1] + dir[1];
                if(eNewX >= 0 && eNewX < totalRow && eNewY >= 0 && eNewY < totalCol && forest.get(eNewX).get(eNewY) != 0) {
                    boolean isDetour = false;
                    if(e[0] <= target[0] && dir[0] == -1) {
                        isDetour = true;
                    }
                    else if(e[0] >= target[0] && dir[0] == 1) {
                        isDetour = true;
                    }
                    else if(e[1] <= target[1] && dir[1] == -1) {
                        isDetour = true;
                    }
                    else if(e[1] >= target[1] && dir[1] == 1) {
                        isDetour = true;
                    }

                    if(isDetour) q.offerLast(new int[]{eNewX, eNewY, e[2] + 1});
                    else q.offerFirst(new int[]{eNewX, eNewY, e[2]});
                }
            }
        }
        return -1;
    }
}

Time Complexity

O(MN * log MN + MN²) Where
M is total number of rows in an input forest
N is total number of cols in an input forest

Space Complexity

O(M * N) Where
M is total number of rows in an input forest
N is total number of cols in an input forest