请求用谷歌Foobar问题进行反向测试案例--准备兔子逃跑[封闭式]。

问题描述 投票：0回答：1

我最近遇到了GoogleFoobar的问题。准备兔子逃跑我提交了一个基于最短路径的解决方案。

然而，只有3 5个案例通过，我真的很想知道为什么。

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

如果有人能 "破解 "我的解决方案，提供一个反案例，告诉我我做错了什么，那将是感激的。

PLEASE DO NOT SEND ME IMPLEMENTATIONS, verbal explanations of my mistakes counter tests would be appreciated.

谢谢。

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)。

写一个函数解(map)，生成从监狱门到逃生舱的最短路径的长度，作为改造计划的一部分，你可以拆除一面墙。路径长度是你经过的节点总数，包括入口和出口节点。起点和终点位置总是可以通过的（0）。地图将始终是可解的，尽管你可能需要或不需要拆除一堵墙。地图的高度和宽度可以从2到20。移動只能沿著心形方向進行，不允許對角線移動。

语言选择

要提供一个Python解决方案，请编辑solution.py要提供一个Java解决方案，请编辑Solution.java。

测试案例

你的代码应该通过以下测试用例，注意，它也可以针对这里没有显示的隐藏测试用例运行。

--Python案例 --Input:solution.solution([[0, 1, 1, 0], [0, 0, 0, 1], [1, 1, 0, 0]]])Output.solution.solution([[0, 1, 1, 0]])输出。 7

输入:solution.solution([[0，0，0，0，0，0]，[1，1，1，1，1，0，0]，[0，1，1，1，1，1，1]，[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，0}，{0，0，0，0，0}，{0，1，1，1，1，1，1}，{0，0，0，0，0}})输出。 11

breadth-first-search dijkstra competitive-coding google-foobar
1个回答
0
投票

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

}

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

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

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.