Google FooBar «Приготовь побег зайчиков» - PullRequest
Новая
       42

Google FooBar «Приготовь побег зайчиков»

0 голосов
/ 19 апреля 2020

В настоящее время я работаю над заданием Google FooBar, и я нахожусь на третьем уровне, на котором я должен найти расстояние между верхней левой и нижней правой точками на сетке. Сетка заполнена единицами и нулями, с нулями, представляющими пересекаемые пробелы, и единицами, представляющими непересекаемые пробелы (типичная сетка будет выглядеть следующим образом): 

[[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]]

В каждой сетке вы должны найти длину (int) кратчайшего маршрута с верхнего слева на нижний правый, но разрешено заменять любой единственный маршрут нулем. , Высота и ширина сетки могут быть где-то между 2 и 20. К сожалению, 2 из 5 тестовых случаев терпят неудачу. Подскажите, пожалуйста, несколько тестовых случаев, когда мой код не запускается. 

import java.util.HashSet;

public class Solution {

    public static int solution(int[][[ arr) {
 
        return (shortestPath(arr, arr.length - 1, arr[0].length - 1, false, new HashSet<>()));


    }

    public static int shortestPath(int[][] array, int r, int c, boolean remodelled, HashSet<Integer> visited) {

        try {
            int k = array[r][c];
        } catch (Exception e) {
            return 1500;
        }

        // generate a unique number for every node to store in HashSet.
        visited.add(20*r + c);

        if (r == 0 && c == 0) {
            visited.remove(20*r + c);
            return 1;
        }

        if (array[r][c] == 1 && !remodelled) {
            array[r][c] = 0;

            int l1;
            if (!visited.contains(20*(r - 1)+c)) {
                l1 = shortestPath(array, r - 1, c, true, visited);
                visited.remove(20 * (r - 1) + c);
            }
            else {
                l1 = 1500;
            }

            int l2;
            if (!visited.contains(20*(r + 1)+c)) {
                l2 = shortestPath(array, r + 1, c, true, visited);
                visited.remove(20 * (r + 1) + c);
            }
            else {
                l2 = 1500;
            }

            int l3;
            if (!visited.contains(20 * r + (c - 1))) {
                l3 = shortestPath(array, r, c -1, true, visited);
                visited.remove(20 * r + (c - 1));
            }
            else {
                l3 = 1500;
            }

            int l4;
            if (!visited.contains(20 * r + (c + 1))) {
                l4 = shortestPath(array, r, c + 1, true, visited);
                visited.remove(20 * r + (c + 1));
            }
            else {
                l4 = 1500;
            }

            array[r][c] = 1;
            return 1 + Math.min(Math.min(l1, l2), Math.min(l3, l4));
        }

        if (array[r][c] == 1 && remodelled) {
            visited.remove(20*r + c);
            return 1500;
        }


        int l1;
        if (!visited.contains(20*(r - 1)+c)) {
            l1 = shortestPath(array, r - 1, c, remodelled, visited);
            visited.remove(20 * (r - 1) + c);
        }
        else {
            l1 = 1500;
        }

        int l2;
        if (!visited.contains(20*(r + 1)+c)) {
            l2 = shortestPath(array, r + 1, c, remodelled, visited);
            visited.remove(20 * (r + 1) + c);
        }
        else {
            l2 = 1500;
        }

        int l3;
        if (!visited.contains(20 * r + (c - 1))) {
            l3 = shortestPath(array, r, c -1, remodelled, visited);
            visited.remove(20 * r + (c - 1));
        }
        else {
            l3 = 1500;
        }

        int l4;
        if (!visited.contains(20 * r + (c + 1))) {
            l4 = shortestPath(array, r, c + 1, remodelled, visited);
            visited.remove(20 * r + (c + 1));
        }
        else {
            l4 = 1500;
        }

        return 1 + Math.min(Math.min(l1, l2), Math.min(l3, l4));

    }

}

ПРИМЕЧАНИЕ: сетка читается с верхним левым как (0,0) и нижним правым как (max_x, max_y).

2 из Три успешно выполненных тестовых примера:

// Тестовый пример 1 - вход: 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

// Тестовый пример 2 - Вход: Solution.solution ({{0, 1, 1, 0}, {0, 0, 0 , 1}, {1, 1, 0, 0}, {1, 1, 1, 0}}) Выход: 7

...