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>() {
            @Override
            public 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;
    }

    @Override
    public 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>

 解题结果