给定一个像board
这样的矩阵,我想找到一条路径,允许我找到更多的数1's
,因为我知道我只能向上(n+1)
向右(m+1)
。我正在尝试使用回溯解决方案,我设法知道在最佳路径上可以找到多少个1's
,但我很难确定如何打印最佳路径的坐标
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))
如何或在何处实现print(n,m)
以打印最佳路径的每个网格的坐标
已编辑
而是想出了这个解决方案
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
首先,您的实现非常低效,因为您多次对单个单元执行
findPath
。例如,如果您有2x2网格,单元格(1,1)将被访问两次:因此,让我们为每个单元格记住
noo
值:其次,在给定的代码中放入
print(n,m)
并不容易,因为对于给定的单元,我们不知道它是否属于任何最佳路径。只有当我们回到cell(0,0)时,我们才能确定这一点但是现在我们有了2d数组}})。让我们实现最佳路径打印机:
noo
:如果noo[i][j]
包含值x
,那么最优方向将是相对于单元格(i,j)到下一个右侧或上一个单元格(i1,j1)和noo[i1][j1] >= x - 1
(noo[i1][j1]
可以等于x
如果board[i][j] == 0
或^请注意,如果
noo[n+1][m]
和noo[n][m+1]
都满足上述条件,则意味着存在多条最佳路径,您可以选择任何方向相关问题 更多 >
编程相关推荐