Given an m-by-n matrix with positive integers, determine the length of the longest path of increasing within the matrix. For example, consider the input matrix:
[1 2 3
4 5 6
7 8 9]
The answer should be 5 since the longest path would be 1-2-5-6-9
def isValid(mat, i, j):
return 0 <= i < len(mat) and 0 <= j < len(mat)
def findLongestPath(mat, i, j):
if not isValid(mat, i, j):
return []
path = []
if i > 0 and mat[i - 1][j] - mat[i][j] == 1:
path = findLongestPath(mat, i - 1, j)
if j + 1 < len(mat) and mat[i][j + 1] - mat[i][j] == 1:
path = findLongestPath(mat, i, j + 1)
if i + 1 < len(mat) and mat[i + 1][j] - mat[i][j] == 1:
path = findLongestPath(mat, i + 1, j)
if j > 0 and mat[i][j - 1] - mat[i][j] == 1:
path = findLongestPath(mat, i, j - 1)
path.insert(0, mat[i][j])
return path
def longestPath(mat):
if not mat or not len(mat):
return []
longest_path = []
for i in range(len(mat)):
for j in range(len(mat)):
path = findLongestPath(mat, i, j)
if len(path) > len(longest_path):
longest_path = path
return len(longest_path)
if __name__ == '__main__':
mat = [
[10, 13, 14, 21, 23],
[11, 9, 22, 2, 3],
[12, 8, 1, 5, 4],
[15, 24, 7, 6, 20],
[16, 17, 18, 19, 25]
]
res = longestPath(mat)
print ("Length of longest path :",res)