用Python严格增加网格中的路径

Question

在每一步，我们可以走一个左，右，上或下的细胞，只有当该细胞是严格更大的，我们目前的细胞。(我们不能对角移动)。我们希望找到从左上角单元格到右下角单元格的所有路径。

[1,4,3，5,6,7]

在我们的例子中，这些路径是1->4->6->7和1->5->6->7。

如何在可逆的情况下解决这个问题？

Answer 1

首先，注意这类路径的数目是指数的(在图的大小上)。

例如，看一下图：

1    2     3   ... n
2    3     4   ... n+1
3    4     5   ... n+2
...
n  (n+1) (n+2) ... 2n

在这里，您完全拥有n权限和n --这给您提供了大量这样的选择--是什么使“高效”解决方案变得无关紧要(正如您所说的，您正在寻找所有路径)。

找到所有解决方案的一种方法是使用DFS的变体，在这种情况下，您可以访问一个邻居单元当且仅当它是更高的。

它应该看起来像：

def Neighbors(grid, current_location):
  """returns a list of up to 4 tuples neighbors to current location"""
  pass  # Implement it, should be straight forward

# Note: Using a list as default value is problematic, don't do it in actual code.
def PrintPaths(grid, current_path = [(0,0)], current_location = (0, 0)):
  """Will print all paths with strictly increasing values.
  """
  # Stop clause: if got to the end - print current path.
  if current_location[0] == len(grid) and current_location[1] == len(grid[current_location[0]):
    print(current_path)
    return
  # Iterate over all valid neighbors:
  for next in Neighbors(grid, current_location):
    if grid[current_location[0]][current_location[1]] < grid[next[0]][next[1]]:
    current_path = current_path + next
    PrintPaths(grid, current_path, next)
    # When getting back here, all that goes through prefix + next are printed.
    # Get next out of the current path
    current_path.pop()