問題描述
刺激基質上的液體流動 (Stimulating Liquid Flow on Matrix)
我必須模擬通過包含一組整數的方陣的液體流動。液體應該從矩陣的左上角開始。它只能向相鄰矩陣的右側或下方移動。相鄰矩陣的值越低,它流動的可能性就越大。液體的運動被認為是在矩陣的右邊緣或下邊緣停止。該程序應該能夠顯示液體通過的所有數字的總和。
import numpy as np
mtr= np.array ([[0, 2, 9],
[4, 9, 8],
[6, 8, 1]])
print(mtr)
def min_adj_val(a, b):
if (a < b):
return a
else:
return b
def min_mtr(mtr, m, n):
if (m == 2 or n == 2):
return mtr[m][n]
else:
return mtr[m][n] + min_adj_val(min_mtr(mtr, m+1, n),min_mtr(mtr, m, n+1))
print(min_mtr(mtr,0, 0))
上面的代碼輸出:10
預期為:11
我希望它是 11,按照路徑 0‑2‑9。但它選擇了成本最低的路徑,即 0‑4‑6。我是初學者,剛學會編碼大約 4 個月。請幫幫我。
參考解法
方法 1:
Each call to min_mtr
will return the shortest length path from (0, 0)
to (m, n)
. When you call min_adj_val
, your arguments are recursive calls to min_mtr
which means that all your function will do is keep the shortest path length it's seen so far and add it to the current index.
A better solution would be to write a greedy function that chooses the min adjacent index and add its value to a running total, moving along until you hit a boundary.
(by Vaneswaran、KuzminK13)