longest_path2.py

class Solution(object):
    def __init__(self):
        self.memo = {}
    
    def is_bounded(self,i,j,matrix):
        return not(i < 0 or j < 0 or i >= len(matrix) or j >= len(matrix[0]))


    def longestIncreasingPathStart2(self, matrix, start_i, start_j, travelled):
        if str([start_i,start_j]) in self.memo:
            return self.memo[str([start_i,start_j])]
        elif travelled[start_i][start_j]:
            return []
        
        travelled[start_i][start_j] = True
        surrounding_indexes = [(start_i-1,start_j),(start_i+1,start_j),(start_i,start_j-1),(start_i,start_j+1)]
        surrounding_indexes = [(i,j) for i,j in surrounding_indexes if self.is_bounded(i,j,matrix)]
        surrounding_indexes = [(i,j) for i,j in surrounding_indexes if matrix[i][j] > matrix[start_i][start_j]]
        longest_paths = [self.longestIncreasingPathStart2(matrix,i,j,travelled) for i,j in surrounding_indexes]
        result = max(longest_paths, key=lambda x: len(x)) + [matrix[start_i][start_j]] if len(longest_paths) > 0 else [matrix[start_i][start_j]]
        self.memo[str([start_i,start_j])] = result
        travelled[start_i][start_j] = False
        return result    


    def longestIncreasingPathStart(self, matrix, start_i, start_j, travelled):
        if str([start_i,start_j]) in self.memo:
            return self.memo[str([start_i,start_j])]
        elif travelled[start_i][start_j]:
            return 0
        
        travelled[start_i][start_j] = True
        surrounding_indexes = [(start_i-1,start_j),(start_i+1,start_j),(start_i,start_j-1),(start_i,start_j+1)]
        surrounding_indexes = [(i,j) for i,j in surrounding_indexes if self.is_bounded(i,j,matrix)]
        surrounding_indexes = [(i,j) for i,j in surrounding_indexes if matrix[i][j] > matrix[start_i][start_j]]
        longest_paths = [self.longestIncreasingPathStart(matrix,i,j,travelled) for i,j in surrounding_indexes]
        result = max(longest_paths) + 1 if len(longest_paths) > 0 else 1
        self.memo[str([start_i,start_j])] = result
        travelled[start_i][start_j] = False
        return result
    
    def longestIncreasingPath(self, matrix):
        if len(matrix) == 0:
            return 0
        travelled = [[False for _ in matrix[0]] for _ in matrix]
        max_length = float("-inf")
        for i in xrange(len(matrix)):
            for j in xrange(len(matrix[0])):
                max_length = max(max_length, self.longestIncreasingPathStart(matrix, i, j, travelled))
        return max_length

    def longestIncreasingPath2(self, matrix):
        if len(matrix) == 0:
            return 0
        travelled = [[False for _ in matrix[0]] for _ in matrix]
        max_length = []
        for i in xrange(len(matrix)):
            for j in xrange(len(matrix[0])):
                max_length = max(max_length, self.longestIncreasingPathStart2(matrix, i, j, travelled), lambda x: len(x))
        return max_length
        
        
s = Solution()                
x = [[9,9,4],[6,6,8],[2,1,1]]
print s.longestIncreasingPath2(x)