Logical Thinking with Java Code Beats 98.04%
Logical Thinking\nSince we always cut off the tree with lowest height first, we collect all trees and sort them by heights. \nIf we make sure we walk the minimu
**Logical Thinking**\nSince we always cut off the tree with lowest height first, we collect all trees and sort them by heights. \nIf we **make sure we walk the minimum steps to cut off each tree**, the sum of these minimum steps will be the final answer.\nFor cutting each tree `(aimX, aimY)`, we implement BFS once:\n**Start point**: `(curX, curY)`\n**Aim point**: `(aimX, aimY)`\n**End point**: `(aimX, aimY)` or `we have no way out`.\n**Transition**:  we try advancing by one step in 4 directions.\n\n**Clear Java Code**\n```\n    private static int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};\n\n    public int cutOffTree(List<List<Integer>> forest) {\n\n        List<int[]> treeHeights = getAllTreeHights(forest);\n        Collections.sort(treeHeights, new Comparator<int[]>() {\n            @Override\n            public int compare(int[] o1, int[] o2) {\n                return o1[2] - o2[2];\n            }\n        });\n        int minSteps = 0;\n        int curX = 0, curY = 0;\n        while (!treeHeights.isEmpty()) {\n            int[] curTree = treeHeights.remove(0);\n            int steps = getMinimumSteps(forest, curX, curY, curTree[0], curTree[1]);\n            if (steps == -1) {\n                return -1;\n            }\n            minSteps += steps;\n            curX = curTree[0];\n            curY = curTree[1];\n            forest.get(curX).set(curY, 1);\n        }\n        return minSteps;\n    }\n\n    private int getMinimumSteps(List<List<Integer>> forest, int curX, int curY, int aimX, int aimY) {\n\n        int minSteps = 0;\n        int rows = forest.size(), cols = forest.get(0).size();\n        boolean[][] visited = new boolean[forest.size()][forest.get(0).size()];\n        Queue<int[]> queue = new LinkedList<>();\n        int startVal = forest.get(curX).get(curY);\n        queue.offer(new int[]{curX, curY});\n        visited[curX][curY] = true;\n\n        while (!queue.isEmpty()) {\n            int size = queue.size();\n            for (int i = 0; i < size; i++) {\n                int[] curCell = queue.poll();\n                if (curCell[0] == aimX && curCell[1] == aimY) {\n                    return minSteps;\n                }\n                for (int[] direction : directions) {\n                    int nx = curCell[0] + direction[0];\n                    int ny = curCell[1] + direction[1];\n                    if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && !visited[nx][ny] && forest.get(nx).get(ny) != 0) {\n                        queue.add(new int[]{nx, ny});\n                        visited[nx][ny] = true;\n                    }\n                }\n            }\n            minSteps++;\n        }\n        return -1;\n    }\n\n    private List<int[]> getAllTreeHights(List<List<Integer>> forest) {\n        List<int[]> treeHeights = new LinkedList<>();\n        for (int i = 0; i < forest.size(); i++) {\n            for (int j = 0; j < forest.get(0).size(); j++) {\n                int tmpVal = forest.get(i).get(j);\n                if (tmpVal > 1) {\n                    int[] element = new int[3];\n                    element[0] = i;\n                    element[1] = j;\n                    element[2] = tmpVal;\n                    treeHeights.add(element);\n                }\n            }\n        }\n        return treeHeights;\n    }\n```\n**I would appreciate your VOTE UP ;)**
[]