Given a matrix like board I want to find the path that allows me to find more number 1's, knowing that I can only go up (n+1) and right (m+1). I'm trying to use a backtracking solution, and I managed to know how many 1's I can find on the best path but I'm having trouble figuring out how to print the coordinates of the best path.
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))
How or where should I implement the print(n,m) to print the coordinates of every grid of the best path
EDITED
Came up with this solution instead
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
At first, your implementation is very inefficient, because you do findPath for a single cell many times. For example, if you have 2x2 grid, cell (1, 1) would be visited two times:
(1, 0) -- path 2 --> (1, 1)
^ ^
| path 2 | path 1
| |
(0, 0) -- path 1 --> (0, 1)
So let's memorise noo value for each cell:
# noo[i][j] == None value means value for cell wasn't calculated before.
# Otherwise noo[i][j] it means calculated answer for cell.
noo=[[None for i in range W] for j in range H]
def findPath(board,n,m):
if noo[n][m] is not None:
return noo[n][m]
noo[n][m] = board[n][m]
if n==len(board)-1 and m==len(board[0])-1:
return noo[n][m]
if n==len(board)-1:
noo[n][m]+=findPath(board,n,m+1)
elif m==len(board[0])-1:
noo[n][m]+=findPath(board,n+1,m)
else:
noo[n][m]+=max(findPath(board,n,m+1),findPath(board,n+1,m))
return noo[n][m]
print(findPath(board,0,0))
How or where should I implement the print(n,m) to print the coordinates of every grid of the best path
At second, there's no easy way to put print(n,m) in the given code, because for a given cell we don't know does it belong to any optimal path or not. We'll know it for sure only when we go back to cell (0, 0).
But now we have 2d array noo: if noo[i][j] contains value x, then optimal will be direction with located relative to cell (i, j) to the next right or up cell (i1, j1) with noo[i1][j1] >= x - 1 (noo[i1][j1] can be equal to x if board[i][j] == 0 or x - 1 if board[i][j] == 1). Let's implement optimal path printer:
def printOptimalPath(n, m):
print(n, m)
if n < len(board)-1 and noo[n + 1][m] == noo[n][m] - board[n][m]:
printOptimalPath(n + 1, m)
elif m < len(board[0])-1 and noo[n][m + 1] == noo[n][m] - board[n][m]:
printOptimalPath(n, m + 1)
# Usage
printOptimalPath(0, 0)
Note, that if both noo[n+1][m] and noo[n][m+1] satisfy conditions described above it means that there is more than one optimal path and you can choose any direction.