我遇到了一个未知输入的StackOverflow异常。我尝试了很多本地测试用例,但没有找到一个能够重现这个问题的。但是当我提交我的代码时,却遇到了这个异常。请问有人能指出我错过的测试用例或提供更好的解决方案吗?
问题和我的代码如下:
您和您所拯救的兔子囚犯需要尽快逃离这个即将崩溃的空间站!不幸的是,一些兔子因长时间囚禁而虚弱无力,跑得很慢。他们的朋友正在帮助他们,但如果您也能加入进来,这次逃脱将会更快捷。防御性舱壁门已经开始关闭,如果你不能及时通过,你将被困住!你需要抓住尽可能多的兔子,在舱壁关闭之前通过。
从起点到达所有兔子和舱壁所需的时间将在一个整数的平方矩阵中给出。每行都会告诉您到达起点,第一只兔子,第二只兔子,...,最后一只兔子和舱壁的时间顺序。行的顺序遵循相同的模式(起点,每只兔子,舱壁)。兔子可以跳到你的怀里,所以捡起它们是瞬间完成的,同时到达封闭舱壁的时间仍然可以成功逃脱,尽管很戏剧化。(别担心,你没捡起来的兔子也能和你一起逃脱,因为它们不再需要携带你捡起来的那些兔子。)如果您愿意,可以重复访问不同的地方,并且移动到舱壁并不意味着您必须立即离开-如果时间允许,您可以在舱壁前后移动以捡起其他兔子。
除了在兔子之间旅行花费时间外,一些路径还与空间站的安全检查点进行交互,并将时间添加回时钟。增加时间将延迟舱壁门的关闭时间,如果时间在舱壁已经关闭后重新变为0或正数,则触发舱壁重新打开。因此,可能会有可能走上一个圆圈并不断获取时间:即每次穿过一条路径时,都使用或添加相同数量的时间。
编写一个形式为 answer(times, time_limit) 的函数,以计算在舱壁永久关闭之前最多可以捡起多少只兔子及它们是哪些兔子。如果有多个大小相同的兔子集合,请按索引号最低的囚犯 ID(作为索引)进行排序,然后返回这个兔子集合。兔子按犯人ID进行排序,第一只兔子的ID是0。最多有5只兔子,time_limit 是一个非负整数,最大值为999。
问题和我的代码如下:
您和您所拯救的兔子囚犯需要尽快逃离这个即将崩溃的空间站!不幸的是,一些兔子因长时间囚禁而虚弱无力,跑得很慢。他们的朋友正在帮助他们,但如果您也能加入进来,这次逃脱将会更快捷。防御性舱壁门已经开始关闭,如果你不能及时通过,你将被困住!你需要抓住尽可能多的兔子,在舱壁关闭之前通过。
从起点到达所有兔子和舱壁所需的时间将在一个整数的平方矩阵中给出。每行都会告诉您到达起点,第一只兔子,第二只兔子,...,最后一只兔子和舱壁的时间顺序。行的顺序遵循相同的模式(起点,每只兔子,舱壁)。兔子可以跳到你的怀里,所以捡起它们是瞬间完成的,同时到达封闭舱壁的时间仍然可以成功逃脱,尽管很戏剧化。(别担心,你没捡起来的兔子也能和你一起逃脱,因为它们不再需要携带你捡起来的那些兔子。)如果您愿意,可以重复访问不同的地方,并且移动到舱壁并不意味着您必须立即离开-如果时间允许,您可以在舱壁前后移动以捡起其他兔子。
除了在兔子之间旅行花费时间外,一些路径还与空间站的安全检查点进行交互,并将时间添加回时钟。增加时间将延迟舱壁门的关闭时间,如果时间在舱壁已经关闭后重新变为0或正数,则触发舱壁重新打开。因此,可能会有可能走上一个圆圈并不断获取时间:即每次穿过一条路径时,都使用或添加相同数量的时间。
编写一个形式为 answer(times, time_limit) 的函数,以计算在舱壁永久关闭之前最多可以捡起多少只兔子及它们是哪些兔子。如果有多个大小相同的兔子集合,请按索引号最低的囚犯 ID(作为索引)进行排序,然后返回这个兔子集合。兔子按犯人ID进行排序,第一只兔子的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]
我的代码 我首先检查是否存在负循环。如果有,那么所有的兔子都可以被救出。如果没有,我就进行深度优先搜索。
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;
}
}