Leetcode675. 为高尔夫比赛砍树:优先队列+广度优先找最短路径

题目连接

675. 为高尔夫比赛砍树

 题目描述

解题思路

当一个图给出来的时候，砍树路径就已经确定了，是根据树的高度进行排序的。那么每次的行走的起点和重点也就确定了，只需要计算从起点到重点的最小值即可。

第一步，遍历整个图，将所有有树的节点假如优先队列。

第二步，从（0，0）起点开始，逐步从优先队列中取点。

第三步，取出的两个点，通过广度优先算法，计算出长度，即可。

解题代码

import com.eclipsesource.json.JsonArray;import java.util.*;public class Solution675 {private List<List<Integer>> tr;private int x;private int y;public static List<List<Integer>> stringToInt2dList(String input) {JsonArray jsonArray = JsonArray.readFrom(input);if (jsonArray.size() == 0) {return new ArrayList<List<Integer>>();}List<List<Integer>> list = new ArrayList<>(jsonArray.size());for (int i = 0; i < jsonArray.size(); i++) {JsonArray cols = jsonArray.get(i).asArray();JsonArray jsonArray2 = JsonArray.readFrom(cols.toString());List<Integer> arr = new ArrayList<>(jsonArray2.size());for (int i1 = 0; i1 < jsonArray2.size(); i1++) {arr.add(jsonArray2.get(i1).asInt());}list.add(arr);}return list;}public static void main(String[] args) {List<List<Integer>> forest1 = stringToInt2dList("[[54581641,64080174,24346381,69107959]," +"[86374198,61363882,68783324,79706116]," +"[668150,92178815,89819108,94701471]," +"[83920491,22724204,46281641,47531096]," +"[89078499,18904913,25462145,60813308]]");List<List<Integer>> forest = stringToInt2dList("[[4,2,3]," +"[0,0,1]," +"[7,6,5]]");int ret = new Solution675().cutOffTree(forest);String out = String.valueOf(ret);System.out.print(out);}private int getMinLen(Pair pair1, Pair pair2) {boolean[][] view = new boolean[x][y];LinkedList<Pair> list = new LinkedList<>();list.add(pair1);int k = 0;while (!list.isEmpty()) {int i = 0;int l = list.size();while (i < l) {Pair p = list.pollFirst();i++;int x0 = p.xx;int y0 = p.yy;if (p.xx == pair2.xx && p.yy == pair2.yy) {return k;} else {if (x0 >= 0 && x0 < x && y0 >= 0 && y0 < y && !view[x0][y0] && tr.get(x0).get(y0) != 0) {Pair up = new Pair(x0 - 1, y0);Pair down = new Pair(x0 + 1, y0);Pair left = new Pair(x0, y0 - 1);Pair right = new Pair(x0, y0 + 1);list.addLast(up);list.addLast(down);list.addLast(left);list.addLast(right);view[x0][y0] = true;}}}k++;}return -1;}public int cutOffTree(List<List<Integer>> forest) {if (forest.get(0).get(0) == 0) {return -1;}this.tr = forest;int x = forest.size();int y = forest.get(0).size();this.x = x;this.y = y;PriorityQueue<Pair> queue = new PriorityQueue<>(new Comparator<Pair>() {@Overridepublic int compare(Pair o1, Pair o2) {return forest.get(o1.xx).get(o1.yy) - forest.get(o2.xx).get(o2.yy);}});for (int i = 0; i < x; i++) {for (int j = 0; j < y; j++) {if (forest.get(i).get(j) > 1) {queue.add(new Pair(i, j));}}}Pair start = new Pair(0, 0);int res = 0;while (!queue.isEmpty()) {Pair target = queue.poll();int dist = getMinLen(new Pair(start.xx, start.yy), new Pair(target.xx, target.yy));if (dist == -1) {return -1;}res += dist;System.out.println(start + "to" + target + dist);start = target;}return res;}
}class Pair {int xx;int yy;public Pair(int xx, int yy) {this.xx = xx;this.yy = yy;}@Overridepublic String toString() {return "Pair{" +"xx=" + xx +", yy=" + yy +'}';}
}

其中，json的解析依赖如下。

        <dependency><groupId>com.eclipsesource.minimal-json</groupId><artifactId>minimal-json</artifactId><version>0.9.5</version></dependency>

 解题结果