Find the Longest Possible Route in a Matrix with Hurdles in Python
The problem in hand is to find the longest possible route in a matrix with hurdles using Python code. Let’s break the information that we have and that we need to find:
- A R x C matrix with hurdles. Let 0’s be hurdles and 1’s be normal elements (R being the number of rows and C number of columns).
- A source element from which we need to start our journey.
- A destination element till which we need to go to complete our journey traversing the longest possible path, avoiding the hurdles.
- We need to find the number of elements that we visited to reach the destination element including the destination element.
NOTE: We have to keep in mind that an element once visited in a particular path cannot be visited again and the route cannot have any diagonal moves. Also, we are allowed to move only to adjacent elements that are not hurdles or 0’s in our case.
EXAMPLE: Let us have a 3 x 10 matrix. Let the hurdles be positioned at (1,2), (1,5), and (1,8) (zero-based indexing). Let the source element be at (0,0) position and the destination be (1,7). Hence, as shown in the attached diagram the length of the longest possible route is 24.
Python Code: Longest Possible Route in a Matrix with Hurdles
Let’s dive into the coding part of the article. So, the idea is to use a function recursively to update the distance and element visited each time until the destination is reached. We start from the source element and look for the path in any of the 4 directions (up, down, left, right). Once we find a path that is allowed we go to the next element. This is repeated until the destination is found or there is no path to move forward. If we reach the destination we update the solution that is the longest path, else if no solution is found we return False.
Python code for the above implementation is:
import sys #Function for finding longest possible route in the matrix with hudles #If the destination is not reachable function returns false #Source Cell=>(i,j) #Destination Cell =>(x,y) def LongestPath(mat,i,j,x,y,visited): #Extracting Rows and columns of matrix mat C=len(mat[1]) R=len(mat) #if source and destination are same return true if i==x and j==y: p=[True,0] return p #if cell is not valid if (i<0 or i>=R or j<0 or j>=C or mat[i][j]==0 or visited[i][j]): p=[False,sys.maxsize] return p #including (i,j) in current path #or setting visited(i,j) to true visited[i][j]=True #storing longest path from current cell (i,j) to destination cell (x,y) res=-sys.maxsize-1 #go left from current cell sol=LongestPath(mat,i,j-1,x,y,visited) #update res => only if destination can be reached on going left from current cell if (sol[0]==True): res=max(res,sol[1]) #go right from current cell sol=LongestPath(mat,i,j+1,x,y,visited) #update res => only if destination can be reached on going right from current cell if (sol[0]== True): res=max(res,sol[1]) #go up from current cell sol=LongestPath(mat,i-1,j,x,y,visited) #update res => only if destination can be reached on going up from current cell if (sol[0]== True): res=max(res,sol[1]) #go down from current cell sol=LongestPath(mat,i+1,j,x,y,visited) #update res => only if destination can be reached on going down from current cell if (sol[0]== True): res=max(res,sol[1]) #Backtrack visited[i][j]= False #return True => if destination can be reached from current cell if (res != -sys.maxsize-1): p=[True,1+res] return p #return False => if destination can't be reached from current cell else : p=[False, sys.maxsize] return p #Wrapper function def FindLongestPath(mat,i,j,x,y): #Extracting Rows and columns of matrix mat C=len(mat[1]) R=len(mat) #initializing a matrix visited that will keep a track with all Falses initially of cells visited visited=[[False for X in range (C)]for Y in range(R)] #find longest route from source to destination and printing its maximum cost p=LongestPath(mat,i,j,x,y,visited) if (p[0]): print("LENGTH OF LONGEST POSSIBLE ROUTE: ",p[1]) #if destination is not reachable else: print("SORRY! DESTINATION CAN'T BE REACHED") #Driver Code #Input Matrix mat=[[1,1,1,1,1,1,1,1,1,1],[1,1,0,1,1,0,1,1,0,1],[1,1,1,1,1,1,1,1,1,1]] #Finding longest path #Source => (0,0) #Destination => (1,7) FindLongestPath(mat,0,0,1,7)
OUTPUT:
LENGTH OF LONGEST POSSIBLE ROUTE: 24
Leave a Reply