Python 递归问题 (Leetcode 542)

Question

我想我误解了 Python 中的一些重要概念，并且它不是 Leetcode 问题所特有的。我非常感谢深入了解 Python 的任何帮助。

Leetcode 542是给定一个仅由 0 和 1 组成的二维数组，并且对于每个 1，找到到达 0 的最短距离。我有一个虚拟 DFS 解决方案:

  class Solution:
    def updateMatrix(self, matrix):
     
      dists = []
      for _ in range(len(matrix)):
          dists.append([0]*len(matrix[0]))
    
      for y in range(len(matrix)):
          for x in range(len(matrix[0])):
              if matrix[y][x] == 1:
                  self.min_dist = len(matrix)+len(matrix[0])
                  self.DFS(x, y, matrix, 0, set({}))
                  dists[y][x] = self.min_dist
                
      return dists

    def DFS(self, x, y, matrix, distance, visited):
    
      if (x, y) in visited or (matrix[y][x] == 1 and distance > self.min_dist): return
    
      if matrix[y][x] == 0:
          print (x, y, "d:", distance)
          print ('------')
          self.min_dist = min(self.min_dist, distance)
          return 
    
      print (x, y, distance)
    
      visited.add((x, y))
    
      if x > 0 and (x-1, y) not in visited: 
          self.DFS(x-1, y, matrix, distance+1, visited)
        
      if y > 0 and (x, y-1) not in visited: 
          self.DFS(x, y-1, matrix, distance+1, visited)
   
      if x < len(matrix[0])-1 and (x+1, y) not in visited: 
          self.DFS(x+1, y, matrix, distance+1, visited)
   
      if y < len(matrix)-1 and (x, y+1) not in visited: 
          self.DFS(x, y+1, matrix, distance+1, visited)
   

简单 DFS 直到达到 0。每次我们调用 DFS，distance + 1。我觉得不错。但是测试用例 input = [[1,0,0],[0,1,1],[1,1,1]] 给了我 dist = [[1,0 ,0],[0,1,1],[1,2,3]].

如果将 matrix[y][x] == 1 更改为 matrix[y][x] == 1 and x==2 and y==2并运行上面的代码，输出为

 2 2 0
 1 2 1
 0 2 2
 0 1 d: 3
 ------
 1 1 2
 0 1 d: 3
 ------
 1 0 d: 3
 ------
 2 1 3
 2 0 d: 4
 ------

在 (x,y)= (2,1) 处，初始距离更改为 3。但 (2,1) 处的初始距离应为 1。我的问题是为什么会发生变化？谁能帮我指出我哪里做错了？谢谢!

Answer 1

你真的不需要递归。您可以简单地将需要更新其邻居的位置排队，并保持更新/排队位置，直到不再进行更新为止:

def getDistances(matrix):
    rows,cols = len(matrix),len(matrix[0])
    maxDist   = rows*cols+1 # start 1's at maximum distance
    result    = [[maxDist*bit for bit in row] for row in matrix]
    more      = { (r,c) for r,row in enumerate(matrix)
                        for c,bit in enumerate(row) if bit == 0}
    while more: # process queue starting with zero positions
        r,c     = more.pop()
        newDist = result[r][c]+1 # neighbours are at distance+1 from here
        for nr,nc in [(r,c+1),(r,c-1),(r+1,c),(r-1,c)]: # 4 directions
            if nr not in range(rows): continue
            if nc not in range(cols): continue            
            if newDist >= result[nr][nc]: continue 
            result[nr][nc] = newDist  # reduce neighbour's distance
            more.add((nr,nc))         # queue neighbour to cascade updates
    return result

输出:

m = [[0,0,0,0,0,1],
     [0,1,1,0,0,0],
     [1,1,1,1,0,1],
     [1,1,1,1,1,0]]

for r in getDistances(m): print(r)
                  
[0, 0, 0, 0, 0, 1]
[0, 1, 1, 0, 0, 0]
[1, 2, 2, 1, 0, 1]
[2, 3, 3, 2, 1, 0]