使用 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()

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

Strictly Increasing Path in Grid with Python

python

algorithm

recursion