Недавно я столкнулся с проблемой 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 и освобождение узников командира Лямбды, но как только они освободятся от тюремных блоков, кроликам нужно будет как можно быстрее покинуть космическую станцию Лямбды через спасательные капсулы. К сожалению, залы космической станции представляют собой лабиринт коридоров и тупиков, которые станут смертельной ловушкой для спасающихся кроликов. К счастью, Commander Lambda назначил вас на проект реконструкции, который даст вам возможность немного облегчить жизнь кроликам. К сожалению (опять же), вы не можете просто устранить все препятствия между кроликами и спасательными капсулами - в лучшем случае вы можете удалить одну стену на путь спасательной капсулы, чтобы сохранить структурную целостность станции и избежать подозрений командира Лямбды.
У вас есть карты частей космической станции, каждая из которых начинается у выхода из тюрьмы и заканчивается у входа в спасательную капсулу. Карта представлена в виде матрицы 0 и 1, где 0 - это проходимое пространство, а 1 - это непроходимые стены. Дверь из тюрьмы находится слева вверху (0,0), а дверь в спасательную капсулу - внизу справа (w-1, h-1).
Напишите функциональное решение (карту), которое генерирует длину кратчайшего пути от двери тюрьмы до спасательного отсека, где вам разрешается удалить одну стену в рамках ваших планов реконструкции. Длина пути - это общее количество узлов, через которые вы проходите, с учетом как входных, так и выходных узлов. Начальная и конечная позиции всегда проходимы (0). Карта всегда будет разрешимой, хотя вам может понадобиться или нет необходимость удалить стену. Высота и ширина карты могут быть от 2 до 20. Движения могут быть сделаны только в основных направлениях; никакие диагональные перемещения не допускаются.
Языки
Чтобы предоставить решение Python, отредактируйте solution.py Чтобы обеспечить решение Java, отредактируйте Solution. java
Контрольные примеры
Ваш код должен пройти следующие контрольные примеры. Обратите внимание, что он также может быть запущен для скрытых тестовых случаев, не показанных здесь.
- Python case - Input: 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
Input: 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