Python的广度优先于谷歌FOO条（准备兔子逃脱）

我工作了下面的问题，我认为我有它主要是解决最短路径，但是一些测试用例执行失败：Python的广度优先于谷歌FOO条（准备兔子逃脱）

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

编写一个函数答案（地图），它可以生成从监狱门到逃生吊舱的最短路径长度，您可以在此处移除一堵墙作为重建计划的一部分。路径长度为您通过的节点总数，同时计入入口和出口节点。起始和结束位置始终可以通过（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,1,1,1,1,1]，[0,1,1,1,1,1]，[0,0,0,0,0,01,35,164,106,1745,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”值（节点是否可以分解的壁）
第三矩阵是具有最短p中更新的对象ATH在该列表中的相应位置上的每个节点
每个阵列的底部右索引（旨在是）的最短路径到“退出”

工作方案对任何人有兴趣

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)

来源

2017-10-09 Mike

您确认当前结果是否正确？请注意，您已颠倒了7和11的顺序。请将您的代码更新为[最小，完整，可验证的示例]（http://stackoverflow.com/help/mcve） - 您有几个实施小规模集成步骤，以及提供缺少的** import **语句。 – Prune

嗨，谢谢你的回应。也许这是一个坏主意，打破我的代码。我很抱歉，因为我认为通过这样做更容易阅读。我已将所有代码合并到一个代码块中，并将其设置为使用可以手动跟踪的更简单的矩阵运行。 – Mike

目前还不清楚你的问题是什么，或者至少它不能从你的描述中重现。你说5个测试用例中有2个失败，但没有关于失败类型（例外？错误结果？...）和失败实例（“情况3和4”？）的信息。这个问题很有趣，我写了一个[小解算器]（https://repl.it/MWXn/9），它可能是也可能不是正确的，可以用来比较/验证解决方案。它的工作方式不同，因为它将问题分解为迷宫解决和墙壁破碎。这效率不高，但更琐碎（在我看来）。 – makadev

秀，看着成拼图，你的代码玩了一会儿（我喜欢拼图......）我觉得主要的问题不是一个简单的错误，但一个简单的错误算法/实施/观后。

让我尝试尽可能解释

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，它更多地取决于环比实际pathes的运行方式。您可以很容易地（很好地不..实际上不那么容易）看到给定的故障问题实例来自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（如评论中所述），则该算法才是正确的。这个算法可能是最好的参考。

来源

2017-10-11 10:15:57 makadev

非常感谢您的支持。因为我找不到失败的测试用例，所以我把头发拉出来。我今天将在这方面开展工作，并会随着我的进展更新你。再次感谢。 – Mike

非常感谢您的帮助。我能解决这个问题，并且用我的工作解决方案编辑了我的原始文章。我失去了可以处理行长不均的矩阵的功能，但我目前正在努力恢复该功能。 – Mike

您的测试案例都解析为最短路径，其中NxN矩阵中的长度为2N-1个节点。你已经打了两除去墙，而不是消除需要测试更多的情况下：

存在路径，而是通过移除壁较短的一个可用
的最短路径是比理论最小
迷宫不是正方形
多的解决方案是可能的;第一壁去除你找到的是不是最好的

另外，我强烈建议你插入一些跟踪仪器仪表：打印报表，可以显示当前部分路径，最佳路径，到目前为止，也许事情的电流调用树（如果这不是当前路径中固有的）。通过简单的代码检查调试是而不是最为人所知的方法。

来源

2017-10-10 00:36:42 Prune

非常感谢您的意见。我编辑了我的帖子，以便我的代码位于可以复制并粘贴并运行的单个块中。此外，我正在通过打印进行调试，但在发布之前我可能会对其进行评论。我也接受了你的建议，并试图拓宽我的测试用例，但它似乎仍然有效。你认为我添加的2个测试用例是好的吗？ – Mike

Python的广度优先于谷歌FOO条（准备兔子逃脱）

回答

相关问题