algorithm - 使用深度优先搜索的迷宫中的最短距离

Question

给定一个 MxN 矩阵，其中每个元素可以是 'o'、's' 或 'g'('s' 和 'g' 是唯一的。只有一个起点和一个终点 ).

假设起始单元格“s”始终位于 (0,0)。

我们想要找到起始单元格“s”与目标单元格“g”之间的最短距离，同时避开障碍物“o”。

例子:

['s', ' ', ' ', ' ', ' ']
[' ', ' ', 'o', 'o', 'o']
['o', ' ', 'o', ' ', ' ']
[' ', ' ', ' ', 'o', ' ']
[' ', ' ', ' ', 'g', ' ']

's' 到 'g' 的最短距离是 7。

我知道我们可以使用广度优先搜索 或hadlock 算法 轻松解决这个问题。但是，我很难理解为什么我的深度优先搜索不起作用。

我正在用 Python 编写，我的代码如下。

class Solution:
   :type maze: list of list
   :type start: tuple
   :type end: tuple
   :rtype: int
   def findShortestDistance(self, maze, start, end):
      self.shortest=math.inf

      #set the default value of visited to be False
      self.visited=defaultdict(lambda: False)

      self.maze=maze
      self.rows=len(maze)
      self.cols=len(maze[0])
      self.depthFirstSearch(0,0,0)
      return self.shortest

   def depthFirstSearch(self, i, j, numStep):
      if i<0 or j<0 or i>=self.rows or j>=self.cols:
         return
      elif self.maze[i][j]=='o':
         return
      elif self.maze[i][j]=='g':
         self.shortest=min(self.shortest,numStep)
         return
      elif self.visited[(i,j)]:
         return

      self.visited[(i,j)]=True

      self.depthFirstSearch(i-1,j,numStep+1)
      self.depthFirstSearch(i,j-1,numStep+1)
      self.depthFirstSearch(i,j+1,numStep+1)
      self.depthFirstSearch(i+1,j,numStep+1)

      self.visited[(i,j)]=False

我真的不明白为什么这行不通，但我无法通过这个问题的几个隐藏测试用例。

此外，有人可以告诉这个算法的运行时间吗？在我看来，它是指数级的。

Answer 1

DFS 在这里不是一个好主意，因为您将不断地重新访问相同的子路径，并且还因为您将不得不探索所有可能的路径以找到最短的路径。一般来说，当您遇到重复工作的递归问题时，您应该考虑动态规划。不过，在这种特定情况下，您可以使用 DFS，这实际上与您针对此问题使用标准 DP 解决方案所做的非常相似。

现在关于您的实现的一些注意事项:

• 通常要避免突变，尤其是在函数算法中。具有副作用而不是返回值的递归函数有点奇怪，尽管可以说它有助于减小堆栈的大小。
• 我发现很难计算复杂度。它基本上等于任何长度的有效路径的数量，所以这是相当大的，特别是当障碍物很少时，因为有许多长度大致等于 n*m 的路径。
• 我找不到你的逻辑本身的问题。您确定它不只是在失败的测试中超时吗？