Google 4级RunningWithTheBunnies StackOverFlow

Question

对于未知的输入，我将面临StackOverFlow异常。我在当地尝试过很多测试案例，但都找不到。但在提交我的解决方案时，我遇到了它。有人能给我指出我错过的测试案例或者建议一个更好的方法吗？

问题和我的代码在下面给出

你和你获救的兔子囚犯需要从太空站坍塌的死亡陷阱中逃出来--而且要快！不幸的是，有些兔子被长期监禁削弱了，不能跑得很快。他们的朋友们正在努力帮助他们，但是如果你也参与进来的话，这次逃跑会快得多。防御性舱门已经开始关闭，如果你不能及时通过，你就会被困住！你需要抓住尽可能多的兔子，并通过舱壁关闭之前。从你的起点移动到所有兔子和舱壁所需的时间将以整数方阵的形式提供给你。每一排都会告诉你开始的时间，第一只兔子，第二只兔子，.，最后一只兔子，以及按顺序排列的舱壁。行的顺序遵循相同的模式(开始，每个兔子，舱壁)。兔子可以跳到你的怀里，所以捡起来是瞬间的，到达舱壁的同时，它的封口仍然允许一个成功的，如果戏剧性，逃跑。(别担心，任何你不接的兔子都能和你一起逃走，因为它们不再需要携带你捡到的兔子了。)如果你愿意的话，你可以重新参观不同的地方，搬到舱壁上并不意味着你必须马上离开--如果时间允许，你可以从舱壁上搬来搬去接更多的兔子。除了花时间在兔子之间旅行外，一些路径还会与空间站的安全检查点交互，并给时钟增加时间。在时钟上增加时间会延迟舱门的关闭，如果时间恢复到0，或者在门已经关闭后有一个正数，就会触发舱壁重新打开。因此，可以在一个圆圈中行走并保持时间:也就是说，每次遍历一条路径时，都会使用或增加相同的时间。写一个函数的形式回答(时间，time_limit)，以计算你能捡到的兔子最多，它们是哪些兔子，同时仍然逃避通过舱壁之前，大门永远关闭。如果有多组大小相同的兔子，则按排序顺序返回具有最低囚犯in (作为索引)的兔子集。兔子被表示为一个按囚犯ID排序的列表，第一个兔子是0。最多有5个兔子，而time_limit是一个非负整数，最多为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算法检查图是否包含负循环，但是您不仅应该检查，还应该删除它们(！)。使用缩减图，您的路径中没有循环，并且最大可能的路径包含5个兔子+入口+出口，因此总共有7个元素没有任何堆栈溢出。

如果顶点上有负循环，您应该先检查它们并返回所有的兔子，如果它们存在的话。如果一个顶点上存在负循环，这意味着你有无限的时间资源，所以你可以收集每一个兔子而不用担心时间。

执行以下步骤：

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