Java using TreeMap. There is extra requirement in the question actually.


  • 0
    Z

    So the method is simple, similar idea with PriorityQueue. Just use treeMap instead.
    But Actually this is a question I did in Amazon OA, if you want to pass all tests, you have one extra requirement: you can not pass the tree with height higher than the tree you previous cut.
    Really simple to solve it, just add an extra condition:
    val <= maxVal
    solution:

    class Solution {
        
        private final int[] dirs_x = new int[]{0, 0, 1, -1};
        private final int[] dirs_y = new int[]{1, -1, 0, 0};
    
        protected int findPath(List<List<Integer>> fields, int[] start, int[] goal, int maxVal) {
    
            if (start[0] == goal[0] && start[1] == goal[1]) return 0;
    
            int n = fields.size();
            if (n == 0) return 0;
            int m = fields.get(0).size();
    
            int[][] path = new int[n][m];
    
            Queue<int[]> q = new LinkedList<>();
            q.offer(start);
    
            while (!q.isEmpty()) {
                int[] src = q.poll();
                for (int i = 0; i < 4; i++) {
                    int x = src[0] + dirs_x[i];
                    int y = src[1] + dirs_y[i];
                    if (x == goal[0] && y == goal[1]) {
                        return 1 + path[src[0]][src[1]];
                    }
    
                    if (x >= 0 && x < n && y >= 0 && y < m) {
                        int val = fields.get(x).get(y);
                        if (val != 0 && path[x][y] == 0) { // should add val <= maxVal
                            path[x][y] = 1 + path[src[0]][src[1]];
                            q.offer(new int[]{x, y});
                        }
                    }
                }
    
            }
    
            return -1;
        }
        
        public int cutOffTree(List<List<Integer>> forest) {
            int numRows = forest.size();
            int numColumns = forest.get(0).size();
            if (numRows <= 0 || numColumns <= 0 || forest == null) return 0;
    
            TreeMap<Integer, int[]> map = new TreeMap<>();
            for (int i = 0; i < numRows; i++) {
                for (int j = 0; j < numColumns; j++) {
                    if (forest.get(i).get(j) > 1) {
                        map.put(forest.get(i).get(j), new int[]{i, j});
                    }
                }
            }
    
            int[] start = new int[]{0, 0};
            int res = 0;
            while (!map.isEmpty()) {
                int height = map.firstKey();
                int[] dest = map.get(height);
                int dist = findPath(forest, start, dest, height);
                if (dist == -1) return -1;
                else {
                    res += dist;
                }
                start = dest;
                map.remove(height);
            }
            return res;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.