Python广度优先算法求解Google foo bar（准备兔子逃跑）的最短路径问题

Question

Python广度优先算法求解Google foo bar（准备兔子逃跑）的最短路径问题

pythonbreadth-first-searchshortest-pathdijkstra

4

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

你有空间站部分地图，每个地图从监狱出口开始并在逃生舱的门口结束。地图表示为0和1的矩阵，其中0是可通过的空间，1是无法通过的墙壁。监狱的出口位于左上角（0,0），进入逃生舱的门位于右下角（w-1,h-1）。

编写一个函数answer(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

如前所述，我认为我已经解决了大部分问题（尽管我不认为我的代码已经优化，我可能是错的），但在隐藏测试用例1到5中，第3和4个测试用例失败。

虽然我绝不指望有人给我答案，但我会很想知道是否有人可以把我引向正确方向。也许有一个边缘情况我没考虑到？也许我犯了一些小错误？也许我的逻辑完全是错的？我从头写了所有代码，并尝试尽可能详细地使用变量名和注释。

我还想提一下，上述的两个测试用例已经通过了。接下来，我将提供我的代码以及一些自己的测试用例。非常感谢您抽出时间听我说。

此外，如果我的代码不够整洁或者有点懒散，请提前谅解。由于在压力下进行复制和粘贴，我尽力保持组织。

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)

- Mike

1

你已经验证了当前的结果是否正确吗？请注意，你已经颠倒了7和11的顺序。请将你的代码更新为最小完整可验证示例 - 你还需要实现一些次要的集成步骤，并提供缺失的import语句。 - Prune

你好，感谢您的回复。也许将我的代码分开是个坏主意。我很抱歉，因为我认为这样做可以使它更易于阅读。我已经将所有的代码合并成一个块，并设置了一个更简单的矩阵，可以手动跟踪运行。 - Mike

你好，测试用例实际上对我是隐藏的，这就是为什么我很难确定我的问题所在。没有输出，只有一条消息说明它失败了，这让我想知道是否我错过了一个边缘情况（我不再相信这是情况）。话虽如此，我的解决方案在行的长度不全相同时会失败，因此我正在努力使其在这种情况下正常工作。 - Mike

2个回答

2

你的测试用例都解决了最短路径问题，在一个NxN矩阵中，长度为2N-1节点。但你需要测试更多情况，其中包括：

存在一条路径，但通过拆除一堵墙可以获得更短的路径
最短路径比理论最小值长
迷宫不是正方形
可能存在多个解决方案；找到的第一堵墙可能不是最佳选择

此外，强烈建议插入一些跟踪工具：打印语句可以显示当前部分路径、到目前为止最佳路径以及当前调用树的一些信息（如果这不是当前路径的固有属性）。通过简单代码检查进行调试并不是最好的方法。

- Prune

非常感谢您的建议。我已经编辑了我的帖子，使我的代码成为一个可以复制、粘贴和运行的单一块。此外，我之前是通过打印来进行调试的，但在发布之前可能已经注释掉了。我也采纳了您的建议，尝试扩大我的测试用例，但似乎仍然有效。您认为我添加的这两个测试用例好吗？ - Mike

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- makadev · Accepted Answer

好的，经过对这个难题的研究和一段时间的代码实践后（我喜欢解谜题...），我认为主要问题不是简单的错误，而是算法/实现/概念本身就有问题。

让我尽可能地解释一下：

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])

在位置A，如果相邻的是墙壁并且在"当前路径"上我们有saldo > 0，那么我们可以打破墙壁并减少saldo，这是可以理解的。

但是如果你看一下位置B和位置C，这是基于邻居/墙壁设置saldo，它更多地取决于循环的运行方式而不是实际路径。你很容易（好吧，实际上并不容易）看到所给出的失败问题实例来自于当墙壁/非墙壁交替时重置saldo。对此也没有真正的修复方法。[需要证明] 基本观点和误解（在我看来）是该算法没有考虑任何给定的节点（网格中的单元格）-除了起点和一些特殊情况之外-都可以是有或没有打破墙壁的路径。你不知道它们中的任何一个是否比另一个更短，因此你基本上需要计算两种情况。

3.如何修正计算？

如果你想坚持使用saldo算法，那么它需要移动到你的BFS中。此外，你还需要注意节点具有两种可能性的情况。

额外说明：我在Stack Exchange Code Review上发现了一个类似的算法（这里），它在BFS中进行saldo计算从当前节点开始。即使答案被接受，只要按照评论中所述替换__eq__检查return self.x == other.x and self.y == other.y and self.saldo == other.saldo，这个算法只有正确的。这个算法可能是最好的参考。