[Java] Sorting + BFS
Idea: Find the order of trees you need to find, BFS between each of the two points to find shortest path between each consective pair of trees (ie shortest path
Idea: Find the order of trees you need to find, BFS between each of the two points to find shortest path between each consective pair of trees (ie shortest path between x1 and x2, then x2 and x3 where xi comes before xj if i < j).\n\n```\nclass Solution {\n    class Triple{\n        int val;\n        int row;\n        int col;\n        public Triple (int val, int row, int col){\n            this.val = val;\n            this.row = row;\n            this.col = col;\n        }\n    }\n    class TripleComparator implements Comparator<Triple>{\n        public int compare(Triple a, Triple b){\n            return a.val - b.val;\n        }\n    }\n    public int cutOffTree(List<List<Integer>> forest) {\n        List<Triple> trees = new ArrayList<>();\n        for(int i = 0; i < forest.size(); i++){\n            for(int j = 0; j < forest.get(i).size(); j++){\n                if(forest.get(i).get(j) > 1) trees.add(new Triple(forest.get(i).get(j), i, j));\n            }\n        }\n        Collections.sort(trees, new TripleComparator());\n        int[][] directions = new int[][] {{1,0}, {-1,0}, {0,-1}, {0,1}};\n        int totalDistance = 0;\n        Triple pastTree = new Triple(0,0,0);\n        for(int i = 0; i < trees.size(); i++){\n            Triple currTree = trees.get(i);\n            int distance = findNextTree(forest, pastTree.row, pastTree.col, currTree.row, currTree.col, directions);\n            if(distance == -1) return -1;\n            totalDistance += distance;\n            pastTree = currTree; \n        }\n        return totalDistance; \n    }\n    //number of edges between nodes, else -1 if unreachable \n    //bfs gives shortest path from one node to another we do this for every pair of nodes\n    private int findNextTree(List<List<Integer>> forest, int sr, int sc, int dr, int dc, int[][] directions){\n        boolean[][] visited = new boolean[forest.size()][forest.get(0).size()];\n        Queue<Triple> bfsQ = new LinkedList<>();\n        bfsQ.offer(new Triple(forest.get(sr).get(sc), sr, sc));\n        int level = -1;\n        while(!bfsQ.isEmpty()){\n            int qSize = bfsQ.size();\n            while(qSize > 0){\n                qSize--;\n                Triple currNode = bfsQ.poll();\n                if(currNode.row == dr && currNode.col == dc) {\n                    level++; \n                    return level;\n                }\n                for(int[] dir : directions){\n                    int nr = dir[0] + currNode.row;\n                    int nc = dir[1] + currNode.col;\n                    if(nr < 0 || nr > forest.size() - 1 || nc < 0 || nc > forest.get(nr).size()-1) continue;\n                    if(visited[nr][nc] || forest.get(nr).get(nc) < 1) continue;\n                    bfsQ.offer(new Triple(forest.get(nr).get(nc), nr, nc));\n                    visited[nr][nc] = true; \n                }\n            }\n            level ++; \n        }\n        return -1; \n    }\n    \n     \n}\n```
[]