Python Google foo bar 的广度优先最短路径（准备兔子逃跑）

Question

我正在处理以下问题，我认为我已经基本解决了它，但是一些测试用例失败了：

You have maps of parts of the space station, each starting at a prison exit and ending at the door to an escape pod. The map is represented as a matrix of 0s and 1s, where 0s are passable space and 1s are impassable walls. The door out of the prison is at the top left (0,0) and the door into an escape pod is at the bottom right (w-1,h-1).

Write a function answer(map) that generates the length of the shortest path from the prison door to the escape pod, where you are allowed to remove one wall as part of your remodeling plans. The path length is the total number of nodes you pass through, counting both the entrance and exit nodes. The starting and ending positions are always passable (0). The map will always be solvable, though you may or may not need to remove a wall. The height and width of the map can be from 2 to 20. Moves can only be made in cardinal directions; no diagonal moves are allowed.

Test cases

Inputs: (int) maze = [[0, 1, 1, 0], [0, 0, 0, 1], [1, 1, 0, 0], [1, 1, 1, 0]]

Output: (int) 7

Inputs: (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]]

Output: (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"值（节点是否可以打破墙）
第三个矩阵是更新后的对象，到列表中相应位置的每个节点的路径最短
每个数组的右下角索引是（旨在）到 "exit"

任何感兴趣的人的工作解决方案

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)

Answer 1

您的测试用例都解析为最短路径，其中 NxN 矩阵的长度为 2N-1 个节点。您同时遇到了拆除墙和不拆除需要测试更多情况：

路径存在，但可以通过移除墙壁获得更短的路径
最短路径比理论最小值长
迷宫不是正方形
可以有多种解决方案；你发现的第一次拆墙不是最好的

此外，我强烈建议您插入一些跟踪工具：可以显示当前部分路径的打印语句、目前为止的最佳路径，也许还有当前调用树的某些内容（如果当前路径不是固有的） ).通过简单的代码检查进行调试是不是最广为人知的方法。

Answer 2

Soo，在研究了那个谜题并玩了一会儿你的代码之后（我喜欢谜题......）我认为主要问题不是一个简单的错误而是一个明显的错误 algorithm/implementation/concept.

让我尽量解释清楚

1。我发现了一个产生错误结果的问题实例：

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

此实例导致 8 的距离，认为它应该是 10，因为 saldo 用于打破墙壁 (0,3) 或 (1,3)绕过 Wall (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.可以理解，如果邻居是Wall，而我们在"current Path"上有saldo > 0，我们可以打破Wall并减少saldo.

但是如果你查看 Position B. 和 Position C.，这是在 neighbor/wall 的基础上设置 saldo 并且它更多地取决于循环的运行方式而不是实际路径。您可以很容易地（嗯，不......实际上不是那么容易）看到给定的失败问题实例来自 wall/non-wall 交替时 saldo 的重置。也没有真正的解决办法。 [需要证明]

基本点和误解（在我看来）是这个算法没有考虑到任何给定节点（网格中的单元格）——除了开始和一些特殊情况——都可以在一个有和没有破墙的路径。你不知道它们中的任何一个是否比另一个短，所以你基本上需要计算这两种情况。

3。那么如何修正计算呢？

如果您不想坚持使用 saldo 的算法，则需要将其移至您的 BFS 中。此外，您需要注意节点具有两种可能性的情况。

附加说明：我偶然发现了一个类似的算法 here on Stack Exchange Code Review，它从当前节点在 BFS 中进行 saldo 计算。即使认为答案已被接受，该算法也只有在替换 __eq__ 检查 return self.x == other.x and self.y == other.y and self.saldo == other.saldo 时才是正确的（如评论中所述）。这个算法可能是最好的参考。

Python Google foo bar 的广度优先最短路径（准备兔子逃跑）

Python breadth first shortest path for Google foo bar (prepare the bunnies escape)

python

breadth-first-search

shortest-path

dijkstra