在每一步，只有當該單元格嚴格大于我們當前的單元格時，我們才能進入左、右、上或下單元格中的一個。（我們不能沿對角線移動）。我們想要找到從左上角單元格到右下角單元格的所有路徑。
[[1,4,3]，[5,6,7]]
在我們的示例中，這些路徑是 1->4->6->7 和 1->5->6->7。
我怎樣才能在可逆使用中解決它？
uj5u.com熱心網友回復：
首先，請注意此類路徑的數量是指數級的（在圖的大小中）。
例如，看圖表：
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()
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/468474.html