Google Foobar Level4 RunningWithTheBunnies测试用例8失败求助

问题说明 #

解Google Foobar Level4的RunningWithTheBunnies题目时仅第8个测试用例失败，参考的同类解决方案均未采用当前思路，需要排查代码逻辑问题。
当前实现思路：采用Floyd-Warshall算法计算全源最短路径、检测负环，贪心选择最近的兔子拾取，最后校验剩余时间是否足够到出口。

题目描述 #

你需要带着尽可能多的兔子在空间站舱门关闭前逃出，给定各点位（起点、兔子点位、出口舱门）间的移动耗时整数方阵，部分路径经过安检点会增加剩余时长，甚至存在可无限刷时长的负环，拾取兔子无耗时，和舱门同时关闭也可逃生，要求返回能带走的数量最多、编号最小的升序兔子ID列表，最多有5只兔子，时间上限最高为999。

实现代码 #

public class RunningWithBunnies {

    public static class FloydWarshall {

        private final Integer[][] allPairShortestPathMatrix;
        private final Integer[][] pathFinderMatrix;

        public FloydWarshall(final Integer[][] matrix) {

            if (matrix.length != matrix[0].length) {
                throw new IllegalArgumentException("Bad Adj Matrix Passed");
            }

            allPairShortestPathMatrix = new Integer[matrix.length][matrix[0].length];
            pathFinderMatrix = new Integer[matrix.length][matrix[0].length];
            for(int i = 0; i < matrix.length; i++) {
                for(int j = 0; j < matrix[i].length; j++) {
                    allPairShortestPathMatrix[i][j] = matrix[i][j];
                    if(matrix[i][j] != null) {
                        pathFinderMatrix[i][j] = j;
                    }
                }
            }
            findAllPairsShortestPath(matrix);
        }

        public int getShortestDistanceBetweenNodes(final int startNode, final int endNode) {
            return allPairShortestPathMatrix[startNode][endNode];
        }

        public List<Integer> findShortestPathBetweenNodes(final int startNode, final int endNode) {

            final List<Integer> path = new ArrayList<>();
            Integer currentNode = startNode;
            path.add(startNode);

            while (currentNode != endNode) {

                currentNode = pathFinderMatrix[currentNode][endNode];
                if (currentNode == null || allPairShortestPathMatrix[currentNode][currentNode] < 0) {
                    return Collections.emptyList();
                }
                path.add(currentNode);
            }

            return new ArrayList<>(path);
        }

        public boolean doesMatrixContainNegativeCycles() {

            for (int i = 0; i < allPairShortestPathMatrix.length; i++) {
                if (allPairShortestPathMatrix[i][i] < 0) {
                    return true;
                }
            }
            return false;
        }

        private void findAllPairsShortestPath(final Integer[][] matrix) {

            for(int k = 0; k < matrix.length; k++) {
                for(int i = 0; i < matrix.length; i++) {
                    for(int j = 0; j < matrix[i].length; j++) {

                        final Integer directPathCost = allPairShortestPathMatrix[i][j];
                        final Integer indirectPathToIntermediateCost = allPairShortestPathMatrix[i][k];
                        final Integer indirectPathFromIntermediateCost = allPairShortestPathMatrix[k][j];

                        if (indirectPathToIntermediateCost != null && indirectPathFromIntermediateCost != null) {
                            if (directPathCost == null ||
                                (directPathCost > indirectPathToIntermediateCost + indirectPathFromIntermediateCost)) {
                                allPairShortestPathMatrix[i][j] = allPairShortestPathMatrix[i][k] + allPairShortestPathMatrix[k][j];
                                pathFinderMatrix[i][j] = pathFinderMatrix[i][k];
                            }
                        }
                    }
                }
            }
        }
    }

    public static int[] solution(int[][] times, int times_limit) {

        final Integer[][] matrix = new Integer[times.length][times[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                matrix[i][j] = times[i][j];
            }
        }
        final FloydWarshall floydWarshall = new FloydWarshall(matrix);

        final Set<Integer> bunniesLeft = IntStream
            .range(1, matrix.length - 1)
            .boxed()
            .collect(Collectors.toSet());

        if (floydWarshall.doesMatrixContainNegativeCycles()) {

            return bunniesLeft
                .stream()
                .mapToInt(bunny -> bunny - 1)
                .toArray();
        }

        final List<Integer[]> path = new ArrayList<>();

        int currentPos = 0;
        int pathCost = 0;
        while (!bunniesLeft.isEmpty()) {

            int nearestBunnyPathDuration = Integer.MAX_VALUE;
            int nearestBunny = -1;
            for (int bunnyPosition : bunniesLeft) {

                if (bunnyPosition != currentPos
                    && bunniesLeft.contains(bunnyPosition)
                    && floydWarshall.getShortestDistanceBetweenNodes(currentPos, bunnyPosition) < nearestBunnyPathDuration) {

                    nearestBunnyPathDuration = floydWarshall.getShortestDistanceBetweenNodes(currentPos, bunnyPosition);
                    nearestBunny = bunnyPosition;
                }
            }

            if (nearestBunny == -1) {
                break;
            }

            final List<Integer> subPath =
                floydWarshall
                    .findShortestPathBetweenNodes(currentPos, nearestBunny)
                    .stream()
                    .filter(bunniesLeft::contains)
                    .collect(Collectors.toList());

            currentPos = nearestBunny;

            for (int subPathNode : subPath) {

                path.add(new Integer[]{
                    subPathNode,
                    path.isEmpty()
                        ? floydWarshall.getShortestDistanceBetweenNodes(0, subPathNode)
                        : pathCost + floydWarshall.getShortestDistanceBetweenNodes(path.get(path.size() - 1)[0], subPathNode)
                });
                bunniesLeft.remove(subPathNode);
                pathCost = path.get(path.size() - 1)[1];
            }
        }

        path.removeIf(pathNode ->
            pathNode[1] + floydWarshall.getShortestDistanceBetweenNodes(pathNode[0], matrix.length - 1) > times_limit
        );

        if (path.isEmpty()) {
            return new int[]{};
        }

        return path
            .stream()
            .mapToInt(node->node[0] - 1)
            .sorted()
            .toArray();
    }
}

逻辑问题点 #

• 负环判断逻辑存在漏洞：当前代码只要检测到图中存在任意负环就直接返回所有兔子，忽略了负环的可达性限制。只有负环同时满足「起点可到达负环」、「负环可到达出口」两个条件时，才能通过刷负环获得无限时长带走所有兔子，若负环是孤立无法到达的，该逻辑会返回错误结果。
• 贪心选兔策略无法得到最优解：题目最多仅有5只兔子，贪心每次选最近的兔子的策略不一定能得到最多的兔子数量。比如存在先拿较远的1只兔子后，剩余时间还能拿3只，总共有4只；但先拿最近的1只后剩余时间只能拿2只，总共有3只的场景，贪心策略会得到更差的结果。
• 末尾路径校验逻辑错误：当前代码直接移除所有「当前节点累计耗时+节点到出口耗时>时间上限」的节点，但删除前面的节点会直接影响后续节点的累计耗时，单独校验单个节点的逻辑完全不成立，会得到错误的可带走兔子列表。
• 相同距离选兔规则不符合要求：遍历未拾取兔子的Set时顺序是无序的，若多个兔子距离当前位置相同，无法保证优先选择编号更小的兔子，不符合题目「数量相同时返回编号最小列表」的要求。

内容的提问来源于stack exchange，提问作者Pratick Roy