Я пытаюсь решить приведенную ниже проблему с помощью foobar. В настоящее время я застрял с двумя неудачными тестами. Ниже приведены постановка задачи и код.
Постановка задачи -
Подготовка к бегству зайчиков
Вы очень близки к уничтожению устройства LAMBCHOP и к освобождению кролика Командующего Лямбды заключенных, но как только они освободятся от тюремных блоков, кроликам нужно будет как можно быстрее покинуть космическую станцию «Лямбда» через спасательные капсулы. К сожалению, залы космической станции представляют собой лабиринт коридоров и тупиков, которые станут смертельной ловушкой для спасающихся кроликов. К счастью, Commander Lambda назначил вас на проект реконструкции, который даст вам возможность немного облегчить жизнь кроликам. К сожалению (опять же), вы не можете просто устранить все препятствия между кроликами и спасательными капсулами - в лучшем случае вы можете удалить одну стену на путь спасательной капсулы, чтобы сохранить структурную целостность станции и избежать подозрений командира Лямбды.
У вас есть карты частей космической станции, каждая из которых начинается у выхода из тюрьмы и заканчивается у входа в спасательную капсулу. Карта представлена в виде матрицы 0 и 1, где 0 - это проходимое пространство, а 1 - это непроходимые стены. Дверь из тюрьмы находится слева вверху (0,0), а дверь в спасательную капсулу - внизу справа (w-1, h-1).
Напишите функциональное решение (карту), которое генерирует длину кратчайшего пути от двери тюрьмы до спасательного отсека, где вам разрешается удалить одну стену в рамках ваших планов реконструкции. Длина пути - это общее количество узлов, через которые вы проходите, с учетом как входных, так и выходных узлов. Начальная и конечная позиции всегда проходимы (0). Карта всегда будет разрешимой, хотя вам может понадобиться или нет необходимость удалить стену. Высота и ширина карты могут быть от 2 до 20. Движения могут быть сделаны только в основных направлениях; никакие диагональные перемещения не допускаются.
Входные данные: 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
Ниже работает код или оба приведенных выше теста.
def cV(v):
#copy the visited matrix
return [ x[:] for x in v]
def move(m, v, i, j, steps, path, modified):
s1 = s2 = 99999
# call solve recursively with copied visited matrix
if m[i][j] == 0:
s1 = solve(m, cV(v), i, j, steps+1, path+[(i,j)], modified)
elif not modified:
s2 = solve(m, cV(v), i, j, steps+1, path+[(i,j,True)], True)
# - picks the least steps among steps taken when a wall is removed and steps taken when a wall is not removed
return min(s1, s2)
def solve(m, v, i, j, steps, path, modified):
r = len(m)
c = len(m[0])
# return teh steps taken if destination is reached
if i == r-1 and j == c-1:
return steps + 1
# mark as visisted
v[i][j] = True
minSteps = [99999]
# loops through each cardinal direction
# move() recursively calls solve
for p in [ [1, 0], [0, 1], [-1, 0], [0, -1] ]:
x, y = i + p[0], j + p[1]
if 0 <= x < r and 0 <= y < c and not v[x][y]:
minSteps.append(
move(m, v, x, y, steps, path, modified)
)
# pick the path with least number of steps
return min(minSteps)
def solution(m):
if len(m) < 2 or len(m[0]) < 2:
return 0
r = len(m)
c = len(m[0])
suM = sum([sum(x) for x in m])
if suM == r * c:
return 0
visited = [[False]*len(x) for x in m]
# helper array to visualize path coordinates
path = []
return solve(m,visited,0,0,0,path,False)
Пожалуйста, помогите мне найти случаи, которые могут быть неудачными? На данный момент: - Тест 1 пройден! - Тест 2 пройден! - Тест 3 не пройден [скрыт] - Тест 4 пройден! [Скрытый] - Тест 5 не пройден [Скрытый]