longest-path-in-matrix.py

# Python3 program to find the longest path in a matrix
# with given constraints

n = 3
# Returns length of the longest path beginning with mat[i][j].
# This function mainly uses lookup table dp[n][n]


def findLongestFromACell(i, j, mat, dp):
    # Base case
    if i < 0 or i >= n or j < 0 or j >= n:
        return 0

    # If this subproblem is already solved
    if dp[i][j] != -1:
        return dp[i][j]

    # To store the path lengths in all the four directions
    x, y, z, w = -1, -1, -1, -1

    # Since all numbers are unique and in range from 1 to n * n,
    # there is atmost one possible direction from any cell
    if j < n - 1 and ((mat[i][j] + 1) == mat[i][j + 1]):
        x = 1 + findLongestFromACell(i, j + 1, mat, dp)

    if j > 0 and (mat[i][j] + 1 == mat[i][j - 1]):
        y = 1 + findLongestFromACell(i, j - 1, mat, dp)

    if i > 0 and (mat[i][j] + 1 == mat[i - 1][j]):
        z = 1 + findLongestFromACell(i - 1, j, mat, dp)

    if i < n - 1 and (mat[i][j] + 1 == mat[i + 1][j]):
        w = 1 + findLongestFromACell(i + 1, j, mat, dp)

    # If none of the adjacent fours is one greater we will take 1
    # otherwise we will pick maximum from all the four directions
    dp[i][j] = max(x, max(y, max(z, max(w, 1))))
    return dp[i][j]


# Returns length of the longest path beginning with any cell
def finLongestOverAll(mat):
    result = 1  # Initialize result
    # Create a lookup table and fill all entries in it as -1
    dp = [[-1 for i in range(n)] for i in range(n)]

    # Compute longest path beginning from all cells
    for i in range(n):
        for j in range(n):
            if dp[i][j] == -1:
                findLongestFromACell(i, j, mat, dp)
            # Update result if needed
            result = max(result, dp[i][j])

    return result


# Driver program
mat = [[1, 2, 9], [5, 3, 8], [4, 6, 7]]
print("Length of the longest path is ", finLongestOverAll(mat))