我最近遇到了GoogleFoobar的问题准备兔子逃生，我提交了一个基于最短路径的解决方案。
然而，只有3/5的病例通过了，我真的很想知道为什么。
我在下面附上了我的代码供参考。
如果有人能"破解"我的解决方案/提供反诉/告诉我我做错了什么，我将不胜感激。
请不要给我发送实施方案，对我的错误/反测试的口头解释将不胜感激。
谢谢
import java.util.PriorityQueue;
public class Solution
{
public static int ans = Integer.MAX_VALUE;
public static int dx [] = {0,0,-1,1};
public static int dy [] = {-1,1,0,0};
static class State implements Comparable<State>
{
int x,y,moves;
boolean wentThroughWall;
public State(int x, int y, int moves, boolean wentThroughWall)
{
this.x = x;
this.y = y;
this.moves = moves;
this.wentThroughWall = wentThroughWall;
}
public int compareTo(State other)
{
return moves - other.moves;
}
}
public static int solution(int[][] map)
{
PriorityQueue<State> enque = new PriorityQueue<State>();
boolean visited [][] = new boolean [map.length][map[0].length];
enque.add(new State(0, 0, 1,false));
while(!enque.isEmpty())
{
State top = enque.poll();
if(top.x == map.length - 1 && top.y == map[0].length - 1)
{
ans = Math.min(ans, top.moves);
continue;
}
if(visited[top.x][top.y])
continue;
visited[top.x][top.y] = true;
for(int i = 0; i < dx.length; i++)
{
int nx = top.x + dx[i];
int ny = top.y + dy[i];
if(nx < 0 || nx >= map.length || ny < 0 || ny >= map[0].length || (map[nx][ny] == 1 && top.wentThroughWall))
continue;
if(map[nx][ny] == 1)
enque.add(new State(nx, ny, top.moves + 1, true));
else
enque.add(new State(nx, ny, top.moves + 1, top.wentThroughWall));
}
}
return ans;
}
public static void main(String[] args) {
int [][] test = {{0, 0, 0, 0, 0, 0}, {1, 1, 1, 1, 1, 0}, {0, 0, 0, 0, 0, 0}, {0, 1, 1, 1, 1, 1}, {0, 1, 1, 1, 1, 1}, {0, 0, 0, 0, 0, 0}};
System.out.println(Solution.solution(test));
}
}
声明：你离摧毁LAMBCHOP末日装置和释放Lambda指挥官的兔子囚犯已经非常近了，但一旦他们离开监狱，兔子们就需要尽快通过逃生舱逃离Lambda的空间站。不幸的是，空间站的大厅是一个由走廊和死胡同组成的迷宫，对于逃跑的兔子来说，这将是一个死亡陷阱。幸运的是，Lambda指挥官让你负责一个改造项目，这将让你有机会让兔子们的事情变得更容易。不幸的是(再次(，你不能只拆除兔子和逃生舱之间的所有障碍物——每个逃生舱路径最多可以拆除一堵墙，既可以保持车站的结构完整性，也可以避免引起兰达指挥官的怀疑。
你有空间站各部分的地图，每个部分从监狱出口开始，到逃生舱的门结束。地图表示为0和1的矩阵，其中0是可通行的空间，1是不可通行的墙。监狱外的门在左上角(0,0(，进入逃生舱的门在右下角(w-1，h-1(。
编写一个功能解决方案(地图(，生成从监狱门到逃生舱的最短路径长度，在那里你可以拆除一面墙，作为改造计划的一部分。路径长度是经过的节点总数，包括入口节点和出口节点。起始位置和结束位置始终可以通过(0(。地图总是可以解决的，尽管你可能需要也可能不需要拆除墙壁。地图的高度和宽度可以在2到20之间。只能在基本方向上移动；不允许对角线移动。
语言
要提供Python解决方案，请编辑solution.py要提供Java解决方案，请编辑solution.Java
测试用例
您的代码应该通过以下测试用例。请注意，它也可以针对此处未显示的隐藏测试用例运行。
--Python案例--输入：solution.solution([0，1，1，0]，[0，0，1]，[1，1，0，0]，[1,1,1,0]](输出：7
输入：solution.solution([0，0，0，0,0]，[1,1,1,1,0]，[0,0,0,0]，[0]，1,1,1,1,1]，[0,1,1,1,11]，[0,1,0,0]](输出：11
--Java案例--输入：解决方案。解决方案(｛｛0，1，1，0｝，｛0、0、1｝、｛1，1、0、0｝、｝(输出：7
输入：解决方案。解决方案(｛0，0，0、0，0｝，｛1，1，1、1、0｝输出：11
Sike，我修复了它。我设法使用随机测试用例生成器生成了一堆测试用例，并意识到我访问的数组没有正确定义。
我在下面列出了正确的解决方案，以供修复时参考。
import java.util.PriorityQueue;
public class Solution
{
public static int ans = Integer.MAX_VALUE;
public static int dx [] = {0,0,-1,1};
public static int dy [] = {-1,1,0,0};
static class State implements Comparable<State>
{
int x,y,moves;
boolean wentThroughWall;
public State(int x, int y, int moves, boolean wentThroughWall)
{
this.x = x;
this.y = y;
this.moves = moves;
this.wentThroughWall = wentThroughWall;
}
public int compareTo(State other)
{
return moves - other.moves;
}
}
public static int solution(int[][] map)
{
PriorityQueue<State> enque = new PriorityQueue<State>();
boolean visited [][][] = new boolean [map.length][map[0].length][2];
enque.add(new State(0, 0, 1,false));
while(!enque.isEmpty())
{
State top = enque.poll();
if(top.x == map.length - 1 && top.y == map[0].length - 1)
{
ans = Math.min(ans, top.moves);
continue;
}
if(visited[top.x][top.y][(top.wentThroughWall ? 0 : 1)])
continue;
visited[top.x][top.y][(top.wentThroughWall ? 0 : 1)] = true;
for(int i = 0; i < dx.length; i++)
{
int nx = top.x + dx[i];
int ny = top.y + dy[i];
if(nx < 0 || nx >= map.length || ny < 0 || ny >= map[0].length || (map[nx][ny] == 1 && top.wentThroughWall))
continue;
if(map[nx][ny] == 1)
enque.add(new State(nx, ny, top.moves + 1, true));
else
enque.add(new State(nx, ny, top.moves + 1, top.wentThroughWall));
}
}
assert(ans != Integer.MAX_VALUE);
return ans;
}
public static void main(String[] args) {
int [][] test = {{0, 0, 0, 0, 0, 0}, {1, 1, 1, 1, 1, 0}, {0, 0, 0, 0, 0, 0}, {0, 1, 1, 1, 1, 1}, {0, 1, 1, 1, 1, 1}, {0, 0, 0, 0, 0, 0}};
System.out.println(Solution.solution(test));
}
}
作为一个有竞争力的人，我想知道我的代码是否真的有效，或者只是弱测试。
如果你发现一个测试用例破坏了我的代码，请在评论中告诉我，我会尽快回复你。