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

MORE TO READ:

1. How to Count maximum points on same line in Python
2. Diagonal traversal of a binary tree in Python