Python ширина первого кратчайшего пути для Google Foo Bar (подготовить побег зайчиков)

Я работаю над следующей проблемой, и я думаю, что она в основном решена, однако некоторые тестовые примеры терпят неудачу:

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

Напишите функциональный ответ (карту), который генерирует длину кратчайшего пути от двери тюрьмы до спасательного отсека, где вам разрешено удалить одну стену в рамках ваших планов реконструкции. Длина пути - это общее количество узлов, через которые вы проходите, с учетом как входных, так и выходных узлов. Начальная и конечная позиции всегда проходимы (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

Как упоминалось ранее, я полагаю, что у меня есть лучшая часть проблемы (хотя я не думаю, что мой код оптимизирован, и я могу ошибаться), но из скрытых тестовых примеров 1–5, 3 и 4 терпят неудачу.

Хотя я ни в коем случае не ожидаю, что кто-нибудь даст мне ответ, мне было бы интересно услышать, может ли кто-нибудь подтолкнуть меня в правильном направлении. Может быть, есть крайний случай, который мне не хватает? Может быть, у меня есть небольшая ошибка где-то? Может быть, моя логика просто неверна? Я написал весь этот код с нуля и постарался быть максимально описательным с моими именами переменных и комментариями.

Я также хотел бы отметить, что вышеупомянутые 2 контрольных примера проходят. Ниже я приведу свой код, а также некоторые из моих собственных тестовых случаев. Спасибо, что нашли время выслушать меня.

Кроме того, я хотел бы заранее извиниться, если мой код неорганизован или неаккуратен. Я много копирую и вставляю и делаю все возможное, чтобы оставаться организованным под давлением.

import sys
import Queue

# 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]]
# maze = [[0, 1, 1, 0], [0, 0, 0, 1], [1, 1, 0, 0], [1, 1, 1, 0]]
# maze = [[0, 1], [1, 0]]
# 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]]
# maze = [[0,1,1,0,0],
#       [0,1,0,1,0],
#       [0,0,0,1,0],
#       ]
# maze = [[0,0,0,0,0],
#       [1,1,1,1,1],
#       [1,1,0,0,1],
#       [0,0,1,0,0],
#       ]
# maze = [[0,1,1],
#       [1,1,1],
#       [0,0,0],
#       ]
# maze = [[0, 1, 1, 0, 1, 0, 0], [0, 0, 0, 0, 1, 1, 0]]
# maze = [[0,0],
#       [0,0],
#       [0,0],
#       [0,0],
#       [0,0],
#       [0,0],
#       [0,0],
#       [0,0],
#       [0,0],
#       [0,0]
#       ]
# maze = [[0,0,1],
#       [0,0,1],
#       [0,0,1],
#       [0,1,1],
#       [1,0,1,1],
#       [0,0,0,0],
#       [0,1,1,0,1],
#       [1,1,1,0,0,0],
#       ]

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

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

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

class Graph():
    def __init__(self, m):
        #create a list of nodes
        self.maze = m
        # self.Nodes = [[None for val in xrange(len(self.maze[0]))] for val in xrange(len(self.maze))]
        self.Nodes = []
        self.visited = Queue.Queue()
        self.saldo = 1
        for rowNum, row in enumerate(m):
            newRow = []
            for colNum, col in enumerate(row):
                #create a node with infinite distance
                #corresponding to the maze index
                # n = Node(sys.maxint, self.saldo)
                n = Node('x', 0)
                n.x = rowNum
                n.y = colNum
                n.value = self.maze[rowNum][colNum]
                #append the node to the graph's list
                # of nodes
                # self.Nodes[rowNum][colNum] = n
                newRow.append(n)
                # self.Nodes.put(n)
            self.Nodes.append(newRow)
            print row

        self.Nodes[0][0].saldo = self.saldo

        print

        for rowNum, row in enumerate(self.Nodes):
            for colNum, node in enumerate(row):
                #set the neighbors of each node by looking at their adjacent
                #nodes, and making sure the list index does not go out of
                #the list bounds
                #also determine whether or not a wall can still be broken down
                #at this node,from this path
                if rowNum > 0:
                    # print rowNum, colNum, len(row) - abs(len(row) - len(self.maze[rowNum - 1]))
                    if len(row) == len(self.Nodes[rowNum - 1]) or colNum < len(row) - abs(len(row) - len(self.maze[rowNum - 1])):
                        if self.maze[rowNum - 1][colNum] == 1:
                            if node.saldo > 0:
                                saldo = node.saldo - 1
                            else:
                                saldo = 0
                            self.Nodes[rowNum - 1][colNum].saldo = saldo
                            node.neighbors.append(self.Nodes[rowNum - 1][colNum])
                        else:
                            if self.Nodes[rowNum - 1][colNum].saldo < node.saldo:
                                self.Nodes[rowNum - 1][colNum].saldo = node.saldo
                            node.neighbors.append(self.Nodes[rowNum - 1][colNum])

                if colNum > 0:
                    if self.maze[rowNum][colNum - 1] == 1:
                        if node.saldo > 0:
                            saldo = node.saldo - 1
                        else:
                            saldo = 0
                        self.Nodes[rowNum][colNum - 1].saldo = saldo
                        node.neighbors.append(self.Nodes[rowNum][colNum - 1])
                    else:
                        if self.Nodes[rowNum][colNum - 1] != None:
                            if self.Nodes[rowNum][colNum - 1].saldo < node.saldo:
                                self.Nodes[rowNum][colNum - 1].saldo = node.saldo
                            node.neighbors.append(self.Nodes[rowNum][colNum - 1])

                if rowNum < len(self.Nodes) - 1:

                    if len(row) > len(self.maze[rowNum + 1]):
                        colLimit = len(self.Nodes[rowNum + 1]) - 1
                    else:
                        colLimit = len(row) - abs(len(row) - len(self.maze[rowNum + 1]))
                        if colLimit < 0:
                            colLimit = 0

                    # print colNum, colLimit
                    # if rowNum == 1 and colNum == 0:
                    #   print len(row), len(self.maze[rowNum + 1]), colNum, colLimit
                    # if len(row) == len(self.maze[rowNum + 1]) or rowNum == 0 or colNum <= colLimit:
                    if colNum <= colLimit:
                        if rowNum == 1 and colNum == 0:
                            print "bottom neighbor"
                        if self.maze[rowNum + 1][colNum] == 1:
                            if node.saldo > 0:
                                saldo = node.saldo - 1
                            else:
                                saldo = 0
                            self.Nodes[rowNum + 1][colNum].saldo = saldo
                            node.neighbors.append(self.Nodes[rowNum + 1][colNum])
                        else:
                            if self.Nodes[rowNum + 1][colNum] != None:
                                if self.Nodes[rowNum + 1][colNum].saldo < node.saldo:
                                    self.Nodes[rowNum + 1][colNum].saldo = node.saldo
                                node.neighbors.append(self.Nodes[rowNum + 1][colNum])

                if colNum < len(row) - 1:
                    if self.maze[rowNum][colNum + 1] == 1:
                        if node.saldo > 0:
                            saldo = node.saldo - 1
                        else:
                            saldo = 0
                        self.Nodes[rowNum][colNum + 1].saldo = saldo
                        node.neighbors.append(self.Nodes[rowNum][colNum + 1])
                    else:
                        if self.Nodes[rowNum][colNum + 1] != None:
                            if self.Nodes[rowNum][colNum + 1].saldo < node.saldo:
                                self.Nodes[rowNum][colNum + 1].saldo = node.saldo
                            node.neighbors.append(self.Nodes[rowNum][colNum + 1])

        #print the saldo values for the maze
        for rowNum, row in enumerate(self.Nodes):
            for colNum, val in enumerate(row):
                print val.saldo,
            print

        #set the initial distance to 1 at the origin
        self.Nodes[0][0].distance = 1

    def shortestDistanceToNode(self):

        #add the origin to the queue
        self.visited.put(self.Nodes[0][0])

        #while there are still nodes in the queue,
        #push the current node's neighbors onto the queue
        #if they are equal to 0, or if a wall can be
        #broken down from this neighbor node
        while not self.visited.empty():
            node = self.visited.get()
            distance = node.distance
            # print "node (", node.x, ",", node.y, ") has", len(node.neighbors), "neighbors" 
            for neighbor in node.neighbors:
                if self.maze[neighbor.x][neighbor.y] == 0 or node.saldo > 0:
                    if distance + 1 < neighbor.distance:
                        # print "node (", node.x, ",", node.y, ") moves to (", neighbor.x, ",", neighbor.y, ")"
                        self.visited.put(neighbor)
                        neighbor.distance = distance + 1

        # for neighbor in self.Nodes[0][1].neighbors:
        #   print "Distance:", self.Nodes[0][1].distance, "x:", neighbor.x, "y:", neighbor.y, "Neighbor Distance:", neighbor.distance

        #print the new node graph with distances based on the
        #shortest path
        print
        for row in self.Nodes:
            for val in row:
                # print "(", val.value, ",", val.distance, ")",
                print val.distance,
            print

        return self.Nodes[len(self.Nodes) - 1][len(self.Nodes[len(self.Nodes) - 1]) - 1].distance

class Node():
    def __init__(self, distance, saldo):
        self.x = 0
        self.y = 0
        self.distance = distance
        self.neighbors = []
        self.saldo = saldo

def answer(maze):
    g = Graph(maze)
    return g.shortestDistanceToNode()

answer(maze)

Вывод для каждого теста с отладкой (в комментариях выше)

Для каждого теста:

  • Первая матрица - это исходный ввод
  • Вторая матрица - это значения "saldo" (может ли узел сломать стену)
  • Третья матрица - это обновленный объект с кратчайшим путем к каждому узлу в соответствующей позиции в списке
  • Нижний правый индекс каждого массива является (должен быть) кратчайшим путем к "выходу"

Рабочее решение для всех, кто заинтересован

import sys
import Queue

# 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]]
# maze = [[0, 1, 1, 0], [0, 0, 0, 1], [1, 1, 0, 0], [1, 1, 1, 0]]
# maze = [[0, 1], [1, 0]]
# 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]]
# maze = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 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, 1, 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, 0],
#         [1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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, 1, 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, 0, 1],
#         [0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1],
#         [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 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, 1, 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, 0],
#         [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0],
#         [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 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, 1, 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, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]

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

maze = [
   [0, 1, 0, 1, 0, 0, 0], 
   [0, 0, 0, 1, 0, 1, 0]
]

class Graph():

    def __init__(self, maze, saldo):
        self.maze = maze
        self.saldo = saldo
        self.rows = len(maze)
        self.columns = len(maze[0])

    def shortestDistanceToEnd(self):

        visited = Queue.Queue()
        # source = Node(0, 0, self.saldo, self.maze, self.maze[0])
        source = Node(0, 0, self.saldo, self.maze)
        visited.put(source)
        distance = {source: 1}

        while not visited.empty():

            node = visited.get()

            if node.rowNum == self.rows - 1 and node.colNum == self.columns - 1:
                return distance[node]

            for neighbor in node.getNeighbors():
                if neighbor not in distance.keys():
                    distance[neighbor] = distance[node] + 1
                    visited.put(neighbor)

        return sys.maxint

class Node:
    # def __init__(self, rowNum, colNum, saldo, maze, row):
    def __init__(self, rowNum, colNum, saldo, maze):
        self.rowNum = rowNum
        self.colNum = colNum
        self.saldo = saldo
        self.maze = maze
        # self.row = row

    def __hash__(self):
        return self.colNum ^ self.rowNum

    def __eq__(self, other):
        return self.rowNum == other.rowNum and self.colNum == other.colNum and self.saldo == other.saldo

    def getNeighbors(self):
        neighbors = []
        rowNum = self.rowNum
        colNum = self.colNum
        saldo = self.saldo
        maze = self.maze
        # row = self.row
        rowLimit = len(maze)
        colLimit = len(maze[0])

        #makes sure we are not going to go passed the left boundary
        if colNum > 0:

            #checks if the node to the left of the current node
            #is a wall
            isAWall = maze[rowNum][colNum - 1] == 1
            if isAWall:
                #checks if this node has the ability to break
                #through a wall
                if saldo > 0:
                    #append a NEW node object to the array of neighbors for
                    #this node. One of my problems with my old version was 
                    #that each node was sharing a pool of references, so
                    #when a new node had the same neighbor as a previous
                    #node, it would overwrite all of its data, which was
                    #causing the algorithm to think it could break through
                    #a wall when it in fact could not
                    # neighbors.append( Node(rowNum, colNum - 1, saldo, maze, maze[rowNum]) )
                    neighbors.append( Node(rowNum, colNum - 1, saldo - 1, maze) )
            else:
                #append a NEW node object to the array of neighbors for
                #this node. One of my problems with my old version was 
                #that each node was sharing a pool of references, so
                #when a new node had the same neighbor as a previous
                #node, it would overwrite all of its data, which was
                #causing the algorithm to think it could break through
                #a wall when it in fact could not
                # neighbors.append( Node(rowNum, colNum - 1, saldo, maze, maze[rowNum]) )
                neighbors.append( Node(rowNum, colNum - 1, saldo, maze) )

        #makes sure we are not going to go passed the right boundary
        if colNum < colLimit - 1:

            #checks if the node to the right of the current node
            #is a wall
            isAWall = maze[rowNum][colNum + 1] == 1
            if isAWall:
                #checks if this node has the ability to break
                #through a wall
                if saldo > 0:
                    neighbors.append( Node(rowNum, colNum + 1, saldo - 1, maze) )
            else:
                #same deal as the above 'if'
                # neighbors.append( Node(rowNum, colNum + 1, saldo, maze, maze[rowNum]) )
                neighbors.append( Node(rowNum, colNum + 1, saldo, maze) )

        #makes sure we are not going to go passed the top boundary
        if rowNum > 0:

            #makes sure we are not checking a value that does not exist
            #in the case that the matrix is not rectangular
            # if len(row) == len(maze[rowNum - 1]) or colNum < len(row) - abs(len(row) - len(maze[rowNum - 1])):

            #checks if the node on top of the current node
            #is a wall
            isAWall = maze[rowNum - 1][colNum] == 1
            if isAWall:
                #checks if this node has the ability to break
                #through a wall
                if saldo > 0:
                    neighbors.append( Node(rowNum - 1, colNum, saldo - 1, maze) )
            else:
                #same deal as the above 'if'
                # neighbors.append( Node(rowNum - 1, colNum, saldo, maze, maze[rowNum]) )
                neighbors.append( Node(rowNum - 1, colNum, saldo, maze) )

        #makes sure we are not going to go passed the bottom boundary
        if rowNum < len(maze) - 1:

            #makes sure we are not checking a value that does not exist
            #in the case the the matrix is not rectangular
            # if len(row) > len(maze[rowNum + 1]):
            #   colLimit = len(maze[rowNum + 1]) - 1
            # else:
            #   colLimit = len(row) - abs(len(row) - len(maze[rowNum + 1]))
            #   if colLimit < 0:
            #       colLimit = 0

            # if colNum < colLimit:
            isAWall = maze[rowNum + 1][colNum] == 1
            if isAWall:
                #checks if this node has the ability to break
                #through a wall
                if saldo > 0:
                    neighbors.append( Node(rowNum + 1, colNum, saldo - 1, maze) )
            else:
                # neighbors.append( Node(rowNum + 1, colNum, saldo, maze, maze[rowNum + 1]) )
                neighbors.append( Node(rowNum + 1, colNum, saldo, maze) )

        return neighbors

def answer(maze):
    g = Graph(maze, 1)
    return g.shortestDistanceToEnd()

print answer(maze)
Источник

2 ответа

Решение

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

Позвольте мне попытаться объяснить это как можно больше

1. Я нашел экземпляр проблемы, который дает неправильный результат:

maze = [
   [0, 1, 0, 1, 0, 0, 0], 
   [0, 0, 0, 1, 0, 1, 0]
]

Этот экземпляр приводит к расстоянию 8 думал, что это должно быть 10 так как saldo используется для разрушения любой стены (0,3) или же (1,3) и дополнительное расстояние необходимо, чтобы обойти стены (0,1) а также (1,5),

2. Глядя в saldo а также neighbor расчет (только один сосед):

if rowNum > 0:
    if len(row) == len(self.Nodes[rowNum - 1]) or colNum < len(row) - abs(len(row) - len(self.maze[rowNum - 1])):
        if self.maze[rowNum - 1][colNum] == 1:
            # Position A.
            if node.saldo > 0:
                saldo = node.saldo - 1
            else:
                saldo = 0
            # Position B.
            self.Nodes[rowNum - 1][colNum].saldo = saldo
            node.neighbors.append(self.Nodes[rowNum - 1][colNum])
        else:
            # Position C.
            if self.Nodes[rowNum - 1][colNum].saldo < node.saldo:
                self.Nodes[rowNum - 1][colNum].saldo = node.saldo
            node.neighbors.append(self.Nodes[rowNum - 1][colNum])

В Position A. Понятно, что если у соседа есть стена, а у нас saldo > 0 на "текущем пути" мы можем сломать стену и уменьшить saldo,

Но если вы посмотрите в Position B. а также Position C.это настройка saldo на основе соседа / стены, и это зависит больше от того, как работает цикл, чем от реальных путей. Вы можете легко (ну, нет.. на самом деле не так просто) увидеть, что данный сбойный экземпляр проблемы возникает в результате сброса saldo когда стена / не стена чередуется. Для этого также нет реального решения. [требуется доказательство]

Основным моментом и неправильным представлением (на мой взгляд) является то, что этот алгоритм не учитывает тот факт, что любой данный узел (ячейка в сетке) - кроме начала и некоторых особых случаев - может быть как на пути с нарушенной, так и без нее. стены. Вы не знаете, короче ли один из них, чем другой, поэтому вам нужно рассчитать оба случая.

3. Так как исправить расчет?

Если вы не хотите придерживаться алгоритма Сальдо, его нужно перенести в BFS. Кроме того, вам нужно позаботиться о случае, когда узел имеет обе возможности.

Дополнительное примечание: я наткнулся на похожий алгоритм здесь в Stack Exchange Code Review, который выполняет вычисления saldo в BFS с текущего узла. Даже если ответ принят, алгоритм верен только в том случае, если вы замените __eq__ проверять return self.x == other.x and self.y == other.y and self.saldo == other.saldo (как указано в комментариях). Этот алгоритм, вероятно, лучший справочник.

Источник

Все ваши контрольные примеры разрешаются по кратчайшему пути, где длина в матрице NxN равна 2N-1 узлам. Вы ударили, удаляя стену и не удаляя, необходимо протестировать больше случаев:

  • Путь существует, но более короткий доступен через удаление стены
  • Кратчайший путь длиннее теоретического минимума
  • Лабиринт не квадратный
  • Возможны несколько решений; первое удаление стены, которое вы найдете, не самое лучшее

Кроме того, я настоятельно рекомендую вам вставить некоторые инструменты трассировки: операторы print, которые могут показать текущий частичный путь, лучший путь на данный момент и, возможно, что-то из текущего дерева вызовов (если это не присуще текущему пути). Отладка простым анализом кода - не самый известный метод.

Источник
Другие вопросы по тегам