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

Question

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

Mik*_*ike 4 python dijkstra breadth-first-search shortest-path

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

你有空间站部分地图，每张地图都从监狱出口开始，到逃生舱门结束。地图表示为 0 和 1 的矩阵，其中 0 是可通行的空间，1 是不可通行的墙。监狱外的门在左上角 (0,0)，逃生舱门在右下角 (w-1,h-1)。

编写一个函数 answer(map) 来生成从监狱门到逃生舱的最短路径的长度，作为改造计划的一部分，您可以在那里拆除一堵墙。路径长度是您通过的节点总数，包括入口节点和出口节点。起始位置和结束位置始终可以通过 (0)。地图将始终是可解的，尽管您可能需要也可能不需要移除墙壁。地图的高度和宽度可以从 2 到 20。移动只能在基本方向上进行；不允许对角移动。

测试用例

输入： (int) 迷宫 = [[0, 1, 1, 0], [0, 0, 0, 1], [1, 1, 0, 0], [1, 1, 1, 0]]

输出： (int) 7

输入： (int) 迷宫 = [[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)

Run Code Online (Sandbox Code Playgroud)

每个测试用例的输出，带调试（在上面的评论中）

对于每个测试用例：

第一个矩阵是原始输入
第二个矩阵是“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

Answer 1

mak*_*dev 6

Soo，在研究了这个谜题并玩了一段时间你的代码之后（我喜欢谜题......）我认为主要问题不是一个简单的错误，而是一个明显错误的算法/实现/概念。

让我尽可能多地解释一下

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

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

Run Code Online (Sandbox Code Playgroud)

这个实例产生了一个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])

Run Code Online (Sandbox Code Playgroud)

在Position A.这是可以理解的，如果邻居是一个墙，我们有saldo > 0“当前路径”，我们可以打破墙壁和减少saldo。

但是，如果您查看Position B.and Position 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（如评论中所述）。这个算法可能是最好的参考。

归档时间：	8 年，1 月前
查看次数：	5142 次
最近记录：	5 年，4 月前