请求带有 Google Foobar 问题的反测试用例 - 准备 Bunnies Escape

Question

我最近遇到了 GoogleFoobar 的问题准备 Bunnies Escape，我提交了一个基于最短路径的解决方案。

然而，只有三分之五的案例通过了，我真的很想知道为什么。

我在下面附上了我的代码以供参考。

如果有人可以"Hack"我的解决方案/提供反例/告诉我我做错了什么，那将不胜感激。

请不要向我发送实现，如果对我的错误/反测试进行口头解释，我们将不胜感激。

谢谢。

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 的兔子囚犯，但是一旦他们离开监狱街区，兔子将需要通过逃生通道 [=59] 逃离 Lambda 的 space 站=] 尽快。不幸的是，space 车站的大厅是一个迷宫般的走廊和死胡同，对于逃跑的兔子来说将是一个死亡陷阱。幸运的是，Lambda 指挥官让你负责一个改造项目，这将使你有机会让兔子们的生活变得更轻松一些。不幸的是（再一次），你不能只移除兔子和逃生之间的所有障碍物 pods - 最多你可以移除每个逃生舱路径的一堵墙，既要保持空间站的结构完整性又要避免唤醒指挥官Lambda 的怀疑。

您有 space 车站部分区域的地图，每个区域都从监狱出口开始，到逃生舱门口结束。地图表示为 0 和 1 的矩阵，其中 0 是可通行的 space，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, 0, 1], [1, 1, 0, 0], [1, 1, 1, 0]]) 输出： 7

输入： solution.solution([[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]]) 输出： 11

-- Java 个案例 -- 输入： Solution.solution({{0, 1, 1, 0}, {0, 0, 0, 1}, {1, 1, 0, 0}, {1, 1, 1, 0}}) 输出： 7

输入： Solution.solution({{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}}) 输出： 11

Answer 1

咳咳，我修好了。我设法使用随机测试用例生成器生成了一堆测试用例，并意识到我访问的数组定义不正确。

我在下面列出了正确的解决方案以供参考。

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));
    }

}

作为一个有竞争力的人，我想知道我的代码是否真的有效，或者只是弱测试。

如果您发现一个测试用例破坏了我的代码，请在评论中告诉我，我会尽快回复您。

请求带有 Google Foobar 问题的反测试用例 - 准备 Bunnies Escape

Request for Counter Testcase with Google Foobar Question - Prepare the Bunnies Escape

dijkstra

breadth-first-search

谢谢。

语言

测试用例