java - 与 Bunnies Stack OverFlow 一起运行的 Google Foobar Level 4

Question

我正面临未知输入的 StackOverFlow 异常。我在本地尝试了很多测试用例，但找不到一个。但是在提交我的解决方案时，我遇到了它。有人可以指出我缺少的测试用例或建议更好的方法吗？

问题和我的代码如下

You and your rescued bunny prisoners need to get out of this collapsing death trap of a space station - and fast! Unfortunately, some of the bunnies have been weakened by their long imprisonment and can't run very fast. Their friends are trying to help them, but this escape would go a lot faster if you also pitched in. The defensive bulkhead doors have begun to close, and if you don't make it through in time, you'll be trapped! You need to grab as many bunnies as you can and get through the bulkheads before they close.

The time it takes to move from your starting point to all of the bunnies and to the bulkhead will be given to you in a square matrix of integers. Each row will tell you the time it takes to get to the start, first bunny, second bunny, ..., last bunny, and the bulkhead in that order. The order of the rows follows the same pattern (start, each bunny, bulkhead). The bunnies can jump into your arms, so picking them up is instantaneous, and arriving at the bulkhead at the same time as it seals still allows for a successful, if dramatic, escape. (Don't worry, any bunnies you don't pick up will be able to escape with you since they no longer have to carry the ones you did pick up.) You can revisit different spots if you wish, and moving to the bulkhead doesn't mean you have to immediately leave - you can move to and from the bulkhead to pick up additional bunnies if time permits.

In addition to spending time traveling between bunnies, some paths interact with the space station's security checkpoints and add time back to the clock. Adding time to the clock will delay the closing of the bulkhead doors, and if the time goes back up to 0 or a positive number after the doors have already closed, it triggers the bulkhead to reopen. Therefore, it might be possible to walk in a circle and keep gaining time: that is, each time a path is traversed, the same amount of time is used or added.

Write a function of the form answer(times, time_limit) to calculate the most bunnies you can pick up and which bunnies they are, while still escaping through the bulkhead before the doors close for good. If there are multiple sets of bunnies of the same size, return the set of bunnies with the lowest prisoner IDs (as indexes) in sorted order. The bunnies are represented as a sorted list by prisoner ID, with the first bunny being 0. There are at most 5 bunnies, and time_limit is a non-negative integer that is at most 999.

For instance, in the case of  
[  
    [0, 2, 2, 2, -1],  # 0 = Start  
    [9, 0, 2, 2, -1],  # 1 = Bunny 0  
    [9, 3, 0, 2, -1],  # 2 = Bunny 1  
    [9, 3, 2, 0, -1],  # 3 = Bunny 2  
    [9, 3, 2, 2,  0],  # 4 = Bulkhead  
]  

时间限制为 1，阵列内部的五个行分别指定起点、兔子 0、兔子 1、兔子 2 和隔板门导出。你可以走这条路:

Start End Delta Time Status
    -   0     -    1 Bulkhead initially open
    0   4    -1    2
    4   2     2    0
    2   4    -1    1
    4   3     2   -1 Bulkhead closes
    3   4    -1    0 Bulkhead reopens; you and the bunnies exit

使用这个解决方案，你会捡起兔子 1 和 2。这是这个空间站走廊的最佳组合，所以答案是 [1, 2]。

测试用例

输入:

(int) times = [[0, 1, 1, 1, 1], [1, 0, 1, 1, 1], [1, 1, 0, 1, 1], [1, 1, 1, 0, 1], [1, 1, 1, 1, 0]]  
(int) time_limit = 3  

输出:

(int list) [0, 1]  

输入:

(int) times = [[0, 2, 2, 2, -1], [9, 0, 2, 2, -1], [9, 3, 0, 2, -1], [9, 3, 2, 0, -1], [9, 3, 2, 2, 0]]  
(int) time_limit = 1  

输出:

(int list) [1, 2]  

我的代码 我基本上做的是首先检查是否存在负循环。如果是，那么所有的兔子都可以获救。如果没有，那么我基本上会做一个 dfs。

import java.io.*;
import java.util.*;


public class RunningWithTheBunnies
{
    public static int maxCount = 0;
    public static int[] toReturn = null;
    public static int[] arr = new int[5];
    public static int rows = 0;
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int rows = Integer.parseInt(br.readLine());
        int[][] times = new int[rows][rows];
        String[] arr = null;
        for(int i = 0 ; i < rows ; i++)
        {
            arr = br.readLine().split(" ");
            for(int j = 0 ; j < rows ; j++)
            {
                times[i][j] = Integer.parseInt(arr[j]);
            }
        }
        int time_limit = Integer.parseInt(br.readLine());
        System.out.println(answer(times,time_limit));
        for(int i = 0 ; i < toReturn.length ; i++)
        {
            System.out.print(toReturn[i] + " ");
        }
        System.out.println("");
    }


    public static int[] answer(int[][] times,int time_limit)
    {
        rows = times.length;
        int containsCycle = containsNegativeCycle(times);
        if(containsCycle == 1){
            System.out.println("has negative cycle");// for degubbing
            toReturn = new int[rows - 2];
            for(int i = 0 ; i < rows - 2 ; i++)
            {
                toReturn[i] = i;
            }
            return toReturn;
        }
        else
        {
            System.out.println("has no negative cycle");// for debugging
            //return new int[2];
            int[] visiting = new int[rows];
            for(int i = 0 ; i < rows ; i++)
            {
                visiting[i] = -2;
            }
            dfs(0,0,time_limit,visiting,times);
            return toReturn;
        }
    }

public static void dfs(int vertex,int count,int timeStatus,int[] visiting,int[][] times)
{
    if(timeStatus < -1)
        return;
    System.out.println("at vertex : " + vertex + ", with status = " + timeStatus);// for debugging purpose.

    visiting[vertex] = timeStatus;
    for(int i = 0 ; i < rows ; i++)
    {
        if(i != vertex && visiting[i] == -2 && timeStatus - times[vertex][i] > -2)
        {
            //arr[count] = i;
            //dfs(vertex,count + 1,timeStatus - times[vertex][i],visiting,times);
            if(i != 0 && i != rows - 1)
            {
                arr[count] = i - 1;
                dfs(i,count + 1,timeStatus - times[vertex][i],visiting,times);
            }
            else
            {
                dfs(i,count,timeStatus - times[vertex][i],visiting,times);
            }
        }
        // else if(i != vertex && (visiting[i] < timeStatus - times[vertex][i] || i == rows - 1 || i == 0) && timeStatus - times[vertex][i] > -2)
         else if(i != vertex && timeStatus - times[vertex][i] > -2)
        {
            dfs(i,count,timeStatus - times[vertex][i],visiting,times);
        }
    }
     if(vertex == rows - 1 && timeStatus >= 0 && arr.length > maxCount)
    {
        toReturn = new int[arr.length];
        for(int i = 0 ; i < arr.length ; i++)
        {
            toReturn[i] = arr[i];
            System.out.println("added " + toReturn[i] + ",at i = " + i );// for debugging
        }
        maxCount = arr.length;
    }

    visiting[vertex] = -2;
}

    public static int containsNegativeCycle(int[][] times)
    {
        int[] dist = new int[rows];
        dist[0] = 0;
        for(int i = 1 ; i < rows ; i++)
        {
            dist[i] = Integer.MAX_VALUE;
        }

        for(int k = 0 ; k < rows - 1 ; k++)
        {
            for(int i = 0 ; i < rows ; i++)
            {
                for(int j = 0 ; j < rows ; j++)
                {
                    if(i != j && dist[i] != Integer.MAX_VALUE)
                    {
                        if(dist[j] > dist[i] + times[i][j])
                        {
                            dist[j] = dist[i] + times[i][j];
                        }
                    }
                }
            }
        }

        for(int i = 0 ; i < rows ; i++)
        {
            for(int j = 0 ; j < rows ; j++)
            {
                if(i != j && dist[j] > dist[i] + times[i][j])
                    return 1;
            }
        }
        return 0;
    }
}

Answer 1

您正在使用 Floyd–Warshall algorithm检查图形是否包含负循环，但您不仅应该检查，还应该删除它们(!)。使用缩减图，您的路径中没有循环，并且最大可能路径包含 5 个兔子 + 入口 + 导出，因此总共 7 个元素没有任何堆栈溢出。

如果顶点上有负循环，您应该首先检查它们并返回所有兔子(如果它们存在)。如果顶点上存在负循环，则意味着您拥有无限的时间资源，因此您可以无忧无虑地收集每只兔子。

执行步骤如下:

1. Reduce graph 去除负循环。
2. 检查顶点上的负循环。
3. 生成所有可能的路径(对于最多 5 个兔子，蛮力是可以接受的)。
4. 按正确顺序选择最佳路径。