Подсказка

У вас есть карты частей космической станции, каждая из которых начинается у выхода из тюрьмы и заканчивается у двери в спасательную капсулу. Карта представлена в виде матрицы из 0 и 1, где 0 — проходимое пространство, а 1 — непроходимые стены. Дверь из тюрьмы находится вверху слева (0,0), а дверь в спасательную капсулу — внизу справа (w-1, h-1).

Напишите функциональный ответ (map), который генерирует длину кратчайшего пути от двери тюрьмы до спасательной капсулы, где вам разрешено удалить одну стену в рамках ваших планов реконструкции. Длина пути — это общее количество узлов, через которые вы проходите, считая как входные, так и выходные узлы. Начальная и конечная позиции всегда проходимы (0). Карта всегда будет разрешима, хотя вам может понадобиться или не понадобиться удалять стену. Высота и ширина карты могут быть от 2 до 20. Ходы могут быть сделаны только в кардинальных направлениях; диагональные ходы не допускаются.

Тестовые примеры

 maze = [
    [0, 0, 1, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 1, 0],
    [1, 1, 1, 1, 0, 1, 1, 1],
    [1, 1, 1, 1, 0, 1, 1, 1],
    [1, 0, 0, 0, 0, 1, 0, 1],
    [1, 0, 1, 1, 1, 1, 0, 0],
    [1, 0, 1, 1, 1, 1, 1, 0],
    [1, 0, 0, 0, 0, 0, 0, 0]
]
#15

maze = [
    [0, 0, 1, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 1, 0],
    [1, 1, 1, 1, 0, 1, 1, 1],
    [1, 1, 1, 1, 0, 1, 1, 1],
    [1, 0, 0, 0, 0, 1, 0, 1],
    [1, 0, 1, 1, 1, 1, 1, 0],
    [1, 0, 1, 1, 1, 1, 1, 0],
    [1, 0, 0, 0, 0, 0, 0, 0]
]
#21

maze = [
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
    [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1],
    [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
]
#39

maze = [
    [0, 1, 0, 1, 0, 0, 0],
    [0, 0, 0, 1, 0, 1, 0]
]
#10
  

Мой код

 from collections import deque


def solution(map):
    H = len(map)
    W = len(map[0])
    start = ((0, 0), False)

    track = {
        (0, 0): (-1, -1)
    }
    to_explore = deque([start])
    visited = set()
    w, h = 0, 0
    while not (w == W-1 and h == H-1):
        current = to_explore.popleft()
        pos, opened = current
        neighbours = get_neighbours(pos)
        zeroes, ones = check_neighbours(neighbours, map, (W, H))
        for node in zeroes:
            if not node in track and node not in visited:
                form_vertex = (node, opened)
                to_explore.append(form_vertex)
                track[node] = pos
        for node in ones:
            if not node in track and node not in visited and not opened:
                form_vertex = (node, True)
                to_explore.append(form_vertex)
                track[node] = pos
        w, h = pos
        visited.add(pos)

    path = []
    current = (W - 1, H - 1)
    while current != (-1, -1):
        path.append(current)
        current = track[current]
    return len(path)


def get_neighbours(pos):
    w, h = pos
    return [(w 1, h), (w-1, h), (w, h 1), (w, h-1)]


def check_neighbours(neighbours, grid, edge):
    zeroes = []
    ones = []
    W, H = edge
    for neighbour in neighbours:
        w, h = neighbour
        if 0 <= w < W and 0 <= h < H:
            value = grid[h][w]
            if value == 0:
                zeroes.append(neighbour)
            else:
                ones.append(neighbour)

    return zeroes, ones
  

Проблема

Насколько я могу судить, код работает. Он проходит все тестовые примеры, которые я бросил на него. Однако он не выполняет два скрытых тестовых примера Google. Может кто-нибудь определить проблему и сказать мне, чего мне не хватает, потому что я исчерпал свои собственные идеи и, похоже, не могу найти, что именно не так.
!! Даже если вы не можете найти решение, неудачные тестовые примеры приветствуются