Подготовьте кроликов к побегу

Эта проблема

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

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

Мой подход примерно следующий:

1. Узнайте набор проницаемые стены (weak_walls) (стена хотя бы с одним соседним соседом свободна
2. если weak_walls пусто (любая модификация бесполезна) вернуть минимальную стоимость, используя BFS
3. В противном случае используйте грубую силу, т.е. переключите каждую стену в weak_walls за один раз и рассчитайте стоимость поездки, наконец, верните минимум всех этих travel_cost

Насколько я тестировал реализацию, приведенную ниже, работает:

from itertools import product
from operator import add, sub
from collections import deque


class CostMap(object):
    def __init__(self, shape):
        assert isinstance(
            shape, (tuple, list)
        ) and (
            len(shape) == 2
        ), 'Invalid / Unsupported shape {}!!'.format(shape)
        self._row_count, self._col_count = shape
        self._cost_map = [
            [float('inf')] * self._col_count
            for _ in range(self._row_count)
        ]

    def is_valid_index(self, point):
        assert isinstance(
            point, (tuple, list)
        ) and (
            len(point) == 2
        ), 'Point {} is invalid!!'.format(point)
        c1 = 0 <= point[0] < self._row_count
        c2 = 0 <= point[1] < self._col_count
        return c1 and c2

    def get_value(self, point):
        assert self.is_valid_index(point=point)
        return self._cost_map[point[0]][point[1]]

    def set_value(self, point, value):
        assert self.is_valid_index(point=point)
        self._cost_map[point[0]][point[1]] = value


class Maze(object):
    free = 0
    wall = 1

    def __init__(self, matrix):
        col_lengths = tuple(set([len(row) for row in matrix]))
        assert len(col_lengths) == 1, 'Maze has inconsistent structure'
        self._row_count = len(matrix)
        self._col_count = col_lengths[0]
        self._adj_matrix = matrix[:]

    def get_maze(self):
        return self._adj_matrix

    def get_shadow(self):
        return Maze(self._adj_matrix[:])

    def get_shape(self):
        return self._row_count, self._col_count

    def get_points(self):
        return product(range(self._row_count), range(self._col_count))

    def is_valid_index(self, point):
        assert isinstance(
            point, (tuple, list)
        ) and (
            len(point) == 2
        ), 'Point {} is invalid!!'.format(point)
        c1 = 0 <= point[0] < self._row_count
        c2 = 0 <= point[1] < self._col_count
        return c1 and c2

    def get_value(self, point):
        assert self.is_valid_index(point=point)
        return self._adj_matrix[point[0]][point[1]]

    def set_value(self, point, value):
        assert self.is_valid_index(point=point)
        self._adj_matrix[point[0]][point[1]] = value

    def is_free(self, point):
        return self.get_value(point) == self.free

    def is_wall(self, point):
        return self.get_value(point) == self.wall

    def get_weak_walls(self):
        weak_walls = set()
        for p in self.get_points():
            if self.is_wall(p) and not(self.is_isolated(p)):
                weak_walls.add(p)
        return weak_walls

    def get_valid_neighbors(self, point):
        assert self.is_valid_index(point=point)
        neighbors = (
            tuple(map(sub, point, (1, 0))),
            tuple(map(sub, point, (0, 1))),
            tuple(map(add, point, (1, 0))),
            tuple(map(add, point, (0, 1)))
        )
        valid_neighbors = set()
        for n in neighbors:
            if self.is_valid_index(n):
                valid_neighbors.add(n)
        return valid_neighbors

    def is_isolated(self, point):
        for neighbor in self.get_valid_neighbors(point):
            if self.is_free(neighbor):
                return False
        return True

    def fare(self, src_point=0, dst_point=-1):
        if src_point == 0:
            src_point = (0, 0)
        if dst_point == -1:
            dst_point = tuple(
                map(
                    sub, self.get_shape(), ([1, ] * len(self.get_shape()))
                )
            )
        assert self.is_valid_index(
            src_point
        ), 'Point {} is invalid!!'.format(src_point)
        assert self.is_valid_index(
            dst_point
        ), 'Point {} is invalid!!'.format(dst_point)
        cost_map = CostMap(self.get_shape())
        cost_map.set_value(point=src_point, value=0)
        visited_points = set()
        queue = deque()
        queue.append(src_point)
        while len(queue) > 0:
            current_point = queue.popleft()
            visited_points.add(current_point)
            if current_point == dst_point:
                break
            else:
                for neighbor in self.get_valid_neighbors(current_point):
                    if self.is_free(neighbor):
                        current_cost = cost_map.get_value(
                            point=current_point
                        ) + 1
                        if current_cost < cost_map.get_value(point=neighbor):
                            cost_map.set_value(
                                point=neighbor, value=current_cost
                            )
                        if not(
                            neighbor in visited_points
                        ) and not(
                            neighbor in queue
                        ):
                            queue.append(neighbor)
        return cost_map.get_value(point=dst_point) + 1


def solution(matrix, src_point=0, dst_point=-1):
    maze = Maze(matrix=matrix)
    weak_walls = maze.get_weak_walls()
    fare = maze.fare(src_point=src_point, dst_point=dst_point)
    if len(weak_walls) == 0:
        return fare
    else:
        for wall in weak_walls:
            maze_mod = maze.get_shadow()
            maze_mod.set_value(point=wall, value=Maze.free)
            fare_mod = maze_mod.fare(src_point=src_point, dst_point=dst_point)
            if fare_mod < fare:
                fare = fare_mod
        return fare

Код работает для следующих тестовых случаев:

maze1 = [
    [0, 1, 1, 0], 
    [0, 0, 0, 1], 
    [1, 1, 0, 0], 
    [1, 1, 1, 0]
]

maze2 = [
    [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]
]
assert solution(maze1) == 7
assert solution(maze2) == 11

Есть ли какие-либо возможные улучшения или оптимизация?

1. Например, можно ли найти решение, не проверяя каждую возможную реконструкцию стены и не пересчитывая стоимость после реконструкции?
2. Есть ли какой-нибудь тестовый пример, когда вышеуказанная реализация не сможет найти решение?