def path(given_map, x, y):
x = given_map[0][0]
y = given_map[0][0]
cnt = 0
if x == len(given_map) and y == len(given_map):
cnt = 1
return cnt
else:
if x < len(given_map) and y < len(given_map):
return path(given_map, x, y)
elif x < len(given_map) and y == len(given_map):
return path(given_map, x, y)
elif x == len(given_map) and y < len(given_map):
return path(given_map, x, y)
else:
cnt = 0
return cnt
if __name__ == '__main__':
input_map = [[1,2,9,4,9],
[1,5,8,7,9],
[9,3,9,9,2],
[2,3,7,5,9],
[1,9,9,1,0]]
print(path(input_map, 0, 0))
input_map = [[1,1,2],
[1,2,2],
[1,2,0]]
print(path(input_map, 0, 0))
必須輸入 n*n 串列以創建一個函式，該函式回傳從起點 [0][0] 到終點 [n-1][n-1] 可以到達的路徑數。
只能向下和向右移動，并且只能按對應的 x 和 y 坐標中顯示的數字向一個方向移動。
不包括移動后地圖外的情況。
以上代碼在我能力范圍內盡量實作。我該如何修改它才能正常運行？
uj5u.com熱心網友回復：
除非您需要使用遞回來實作這一點，否則我建議使用 BFS（廣度優先搜索）方法使用字典來跟蹤您在行程的每個步驟中達到的位置/計數：
def path(M):
result = 0 # final result
bounds = range(len(M)) # inside map
paths = {(0,0):1} # one path at start
while paths: # spread counts
nextPos = dict() # track next positions
for (x,y),count in paths.items(): # extend positon/count
if x == y == len(M)-1: result = count # capture final count
dist = M[x][y] # travel distance
if not dist: continue # no movement ...
for x2,y2 in [(x,y dist),(x dist,y)]: # travel down & right
if x2 in bounds and y2 in bounds: # propagate count
nextPos[x2,y2] = nextPos.get((x2,y2),0) count
paths = nextPos # next step on paths
return result
input_map = [[1,2,9,4,9],
[1,5,8,7,9],
[9,3,9,9,2],
[2,3,7,5,9],
[1,9,9,1,0]]
print(path(input_map)) # 2
input_map = [[1,1,2],
[1,2,2],
[1,2,0]]
print(path(input_map)) # 1
如果您需要實作遞回方法，則可以像這樣調整該函式（回傳遞回路徑計數的總和），但它不再是 BFS：
def path(M,x=0,y=0):
if x == y == len(M)-1: return 1 # goal reached
dist = M[x][y] # travel distance
if not dist: return 0 # no movement
bounds = range(len(M)) # inside map
return sum(path(M,x2,y2) for x2,y2 in [(x,y dist),(x dist,y)]
if x2 in bounds and y2 in bounds) # sum of paths
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/370731.html