У меня возникли проблемы с решением вопроса Google Foobar, связанного с поиском пути. В моем решении не выполняется 2 тестовых примера, входные и выходные данные которых скрыты.

Подсказка:

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

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

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

Входные данные: (int) maze = [[0, 1, 1, 0], [0, 0, 0, 1], [1, 1, 0, 0], [1, 1, 1, 0]]

Вывод: (int) 7

Входные данные: (int) maze = [[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) 11

Мой код:

 from queue import PriorityQueue

# Grid class
class Grid:
    # Initialized with dimensions to check later if all neighbor points are actually within the graph
    def __init__(self, width, height):
        self.width = width
        self.height = height
        self.walls = []
        self.weights = {}
        self.wall_count = 0

    # Find the cost of a certain destination node
    # Cost is reported as a tuple to account for going across a wall: (# of moves through a wall, # of normal moves)
    def cost(self, from_node, to_node):
        if to_node in self.walls:
            return self.weights.get(to_node, (1, 0))
        else:
            return self.weights.get(to_node, (0, 1))

    # Check if the location is actually within the graph
    def in_bounds(self, id):
        (x, y) = id
        return 0 <= x < self.width and 0 <= y < self.height

    # Find the adjacent nodes of a node (ie. the places it can go to)
    # Filters out any result which isn't on the graph using self.in_bounds
    def neighbors(self, id):
        (x, y) = id
        results = [(x 1, y), (x, y-1), (x-1, y), (x, y 1)]
        if (x   y) % 2 == 0: results.reverse() # aesthetics
        results = filter(self.in_bounds, results)
        return results

# Find the dimensions of the 2D list by finding the lengths of the outer and inner lists
def dimensions_2d(xs):
    width = len(xs)
    height = len(xs[0])
    return (width, height)

# Returns all the positions of an element in a 2D list
# In this case it's used to find all walls (occurences of 1) to pass to the Grid object
def index_2d(xs, v):
    results = [(x, y) for y, ls in enumerate(xs) for x, item in enumerate(ls) if item == v]
    return results

# Djikstra search algorithm; mistakenly named "a_star" before
# Returns both a dictionary of "destination" locations to "start" locations (tuples) as well as a dictionary of the calculated cost of each location on the grid
def djikstra_search(graph, start, goal):
    # Priority Queue to select nodes from
    frontier = PriorityQueue()
    # Place our starting cost in
    frontier.put(start, (0, 0))

    came_from = {}
    cost_so_far = {}
    came_from[start] = None
    cost_so_far[start] = (0, 0)

    while not frontier.empty():
        # Get the element with the highest priority from the queue
        current = frontier.get()

        if current == goal:
            break

        # For every neighbor of the selected node
        for next in graph.neighbors(current):
            # The new cost of the neighbor node is current cost plus cost of this node - (1, 0) if it goes through a wall, (0, 1) otherwise
            new_cost = (cost_so_far[current][0]   graph.cost(current, next)[0], cost_so_far[current][1]   graph.cost(current, next)[1])
            # If the node has not cost currently
            # OR if the number of walls traveled through is less than the current cost
            # AND if the number of normal steps taken is less than or the same as the current number
            if next not in cost_so_far or (new_cost[0] < cost_so_far[next][0] and sum(new_cost) <= sum(cost_so_far[next])):
                # Record it in both the cost and came_from dicts
                cost_so_far[next] = new_cost
                # Place the cost in the queue
                priority = new_cost
                frontier.put(next, priority)
                came_from[next] = current

    return came_from, cost_so_far

# Find the length of the calculated path
# Using the returned list of edges from djikstra_search, move backwards from the target end and increment the length until the start element is reached
def path(grid, start, end):
    # Perform the search
    path = djikstra_search(grid, start, end)
    search = path[0]

    # If the end element's cost travels through more than 1 wall return 0
    if path[1].get(end)[0] > 1:
        return 0

    # Otherwise move backwards from the end element and increment length each time
    # Once the start element has been reached, we have our final length
    length = 1
    last = end
    while last != start:
        last = search.get(last)
        length  = 1

    return length

# The "main" function
def answer(maze):
    # Find all occurences of walls (1) in the 2D list
    walls = index_2d(maze, 1)
    # Find the x and y dimensions of the maze (required for the Grid object)
    dims = dimensions_2d(maze)
    # Create a new grid with our found dimensions
    grid = Grid(dims[0], dims[1])

    # The start point will always be at (0,0) and the end will always be at the bottom-right so we define those here
    start = (0, 0)
    end   = (dims[0] - 1, dims[1] - 1)

    # the walls variable's locations are flipped, so reverse each of them to get the right wall positions
    grid.walls = [(y, x) for x, y in walls]

    # Return the length
    return path(grid, start, end)
  

В моем собственном тестировании (сетки до 7×7) это решение, похоже, работает без проблем.

Любая помощь (или неудачные случаи) будут высоко оценены!

Логические:

Вопрос можно решить с помощью BFS со следующими изменениями:

1. Каждый путь, который в противном случае имел бы все 0 в стандартном алгоритме BFS, может иметь один 1.

2. В очереди BFS каждый узел, помимо отслеживания координат x и y, также будет хранить количество шагов (длину пути), предпринятых для достижения этого места, и если путь для этого узла уже пройден за 1 или нет. Итак, каждый узел в queue будет иметь формат — [[row, col], num_steps, one_traversed] .

   Таким образом, хотя может показаться, что нам нужно сохранить все пути в обходе BFS, на самом деле нам нужно сохранить, был ли пройден 1 в пути или нет. Таким образом, каждый узел будет хранить эту информацию для себя.

3. Мы будем поддерживать visited сетку, которая будет отслеживать все посещенные узлы (чтобы избежать циклов), но вот сложная часть — вместо того, чтобы иметь только 1 и 0 для представления посещенных или нет, эта сетка будет иметь 4 возможных значения:

   • -1 является начальным значением
   • 0 означает, что путь посещается путем, НЕ имеющим 1s (все 0s)
   • 1 означает, что путь, имеющий 1
   • 2 означает, что пути посещаются обоими типами

   Причина:

   В то время как в обычных вопросах BFS мы избегаем посещения узла после того, как он был посещен один раз, в этой задаче каждый узел в maze можно посетить дважды, прежде чем он будет помечен как не посещаемый снова. Это потому, что:

   • Если узел посещается в первый раз по пути, состоящему всего из 0, его не следует посещать повторно по любому другому пути, состоящему только из 0, поскольку этот другой путь будет либо такой же длины (в этом случае это не имеет значения), либо длиннее (в этом случае мы в любом случаене хотелось бы рассматривать это, поскольку этот путь достигает узла, который уже пройден более коротким путем, состоящим из всех 0).

     Та же логика применима к узлу, который был посещен путем, который прошел через 1, и теперь снова посещается путем, имеющим 1 (мы отвергнем более поздний путь, поскольку он либо такой же, либо длиннее первого пути).

   • Однако, если узел, который ранее посещался путем, имеющим 1, теперь посещается путем, имеющим только 0, мы хотим рассмотреть и этот более поздний путь. Почему? Поскольку возможно, что более ранний путь, который достиг этого узла после прохождения 1, может не достичь пункта назначения, поскольку он может достичь точки, где ему нужно пройти еще 1 для достижения пункта назначения, но поскольку он уже прошел 1, он не может двигаться дальше. Итак, этот новый путь, который может быть длиннее предыдущего, но еще не прошел 1, может пройти дополнительный 1.

     Пример

     

     В этом примере, хотя красный путь [2, 0] сначала достигает узла, это неправильный путь, поскольку он блокируется [3, 0] . Поэтому мы должны также учитывать зеленый путь для прохождения [2, 0] , даже если он длиннее красного.

И, наконец, базовый вариант — остановиться, когда вы достигнете нижнего правого узла в maze . (В вопросе указано, что всегда будет решение, поэтому нет проверки на случай отсутствия решения.)

Код:

 grid = [[0, 0, 0, 0],
[1, 1, 1, 0],
[0, 0, 0, 0],
[1, 1, 1, 1],
[0, 1, 1, 1],
[0, 0, 0, 0]]  # using the name grid instead of maze

num_rows = len(grid)
num_cols = len(grid[0])

def is_valid(r, c):
    return True if (0 <= r < num_rows and 0 <= c < num_cols) else False

def get_neighbours(r, c):
    up = [r - 1, c]
    down = [r   1, c]
    left = [r, c - 1]
    right = [r, c   1]

    neighbours = [down, right, up, left]
    valid_neighbour = list()

    for neighbour in neighbours:
        if is_valid(*neighbour):
            valid_neighbour.append(neighbour)

    return valid_neighbour

# queue format is [[row, col], num_steps, one_traversed]
queue = [[[0, 0], 1, 0]]

cols = list()
visited = list()

# visited matrix is used to keep track of visited nodes:
# -1 is default
# 0 means visited by a path having no 1s
# 1 means visited by a path having a 1
# 2 means visited by both paths - having 1 and 0s
for j in range(num_rows):
    visited.append([-1] * num_cols)

visited[0][0] = 0

# BFS
while queue:
    current_node = queue.pop(0)

    r, c, num_steps, one_traversed = current_node[0][0], current_node[0][
        1], current_node[1], current_node[2]

    # Base Case
    if r == num_rows - 1 and c == num_cols - 1:
        print(num_steps)

    neighbours = get_neighbours(r, c)

    for neighbour in neighbours:
        if visited[neighbour[0]][neighbour[1]] in [0, 1]:
            # the current node was previously visited with opposite one_traversed value, so consider it
            if visited[neighbour[0]][neighbour[1]] != one_traversed:
                one_traversed_now = 1 if grid[neighbour[0]][neighbour[1]] == 1 else one_traversed
                visited[neighbour[0]][neighbour[1]] = 2

                queue.append([[neighbour[0], neighbour[1]], num_steps   1, one_traversed_now])
        elif visited[neighbour[0]][neighbour[1]] == -1:
            if grid[neighbour[0]][neighbour[1]] == 1 and one_traversed == 1:
                continue

            one_traversed_now = 1 if grid[neighbour[0]][neighbour[1]] == 1 else one_traversed

            visited[neighbour[0]][neighbour[1]] = one_traversed_now
            queue.append([[neighbour[0], neighbour[1]], num_steps   1, one_traversed_now])
  

Примеры тестовых примеров: