給定一個(gè)像board的矩陣，我想找到一條路徑，讓我找到更多的數(shù)1's，知道我只能向上(n+1)和右(m+1)。我正在嘗試使用回溯解決方案，我設(shè)法知道在最佳路徑上可以找到多少1's，但我無法計(jì)算出如何打印最佳路徑的坐標(biāo)。
board=[[0,0,0,0,1,0],
[0,1,0,1,0,0],
[0,0,0,1,0,1],
[0,0,1,0,0,1],
[1,0,0,0,1,0]]
def findPath(board,n,m):
noo=0
if board[n][m]>0:
noo+=1
if n==len(board)-1 and m==len(board[0])-1:
return noo
if n==len(board)-1:
noo+=findPath(board,n,m+1)
elif m==len(board[0])-1:
noo+=findPath(board,n+1,m)
else:
noo+=max(findPath(board,n,m+1),findPath(board,n+1,m))
return noo
print(findPath(board,0,0))
我應(yīng)該如何或在哪里實(shí)現(xiàn)print(n,m)來打印最佳路徑的每個(gè)網(wǎng)格的坐標(biāo)
EDITED
而是想出了這個(gè)解決方案
def path(board,x,y,xl,yl,sol,index,paths):
sol.append([x,y])
solaux=sol
if x==0 and y==0:
pass
if board[x][y]>0:
sol[0]+=1
if x==xl-1 and y==yl-1:
paths.append(sol)
print(sol)
return paths
if x==xl-1:
path(board,x,y+1,len(board),len(board[0]),sol,index,paths)
elif y==yl-1:
path(board,x+1,y,len(board),len(board[0]),sol,index,paths)
else:
index= len(sol)
auxnoo= sol[0]
path(board,x,y+1,len(board),len(board[0]),sol,index,paths)
sol = sol[0:index]
sol[0]=auxnoo
path(board,x+1,y,len(board),len(board[0]),sol,index,paths)
return paths
一開始，您的實(shí)現(xiàn)效率非常低，因?yàn)槟啻螌蝹€(gè)單元執(zhí)行
findPath。例如，如果您有2x2網(wǎng)格，則單元（1，1）將被訪問兩次：讓我們記住每個(gè)單元格的
noo值：其次，沒有簡單的方法將
print(n,m)放入給定的代碼中，因?yàn)閷τ谝粋€(gè)我們不知道它是否屬于任何最優(yōu)路徑的給定單元。只有當(dāng)我們回到cell（0，0）時(shí)我們才能確定它。但是現(xiàn)在我們有了2d數(shù)組
noo：如果noo[i][j]包含值x，那么最佳方向?qū)⑹窍鄬τ趩卧瘢╥，j）到下一個(gè)右上單元格（i1，j1）的noo[i1][j1] >= x - 1（noo[i1][j1]可以等于x如果board[i][j] == 0或x - 1如果board[i][j] == 1）。讓我們實(shí)現(xiàn)最佳路徑打印機(jī)：注意，如果
noo[n+1][m]和noo[n][m+1]都滿足上述條件，則意味著存在不止一條最佳路徑，您可以選擇任何方向。