class Solution {
    std::vector<std::vector<int>> longPath;
    int maxi;
    int m, n;
    int DFS(vector<vector<int>>& matrix, int row, int col, int prev) {
        if (row<0||col<0||row>=m||col>=n) {
            return 0;
        }
        if (matrix[row][col]>prev) {
            if (longPath[row][col]>=0)
                return longPath[row][col];

            longPath[row][col] = 1+std::max({DFS(matrix, row+1, col, matrix[row][col]),
            DFS(matrix, row-1, col, matrix[row][col]),
            DFS(matrix, row, col+1, matrix[row][col]),
            DFS(matrix, row, col-1, matrix[row][col])});
            return longPath[row][col];
        }
        else
            return 0;
    }
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if (matrix.empty())
            return 0;
        m = matrix.size();
        n = matrix[0].size();
        maxi = 0;
        longPath = std::vector<std::vector<int>> (m, std::vector<int>(n,-1));

        for (int ii=0; ii<m; ++ii) {
            for (int jj=0; jj<n; ++jj) {
                if (longPath[ii][jj]==-1) {
                    DFS(matrix, ii, jj, std::numeric_limits<int>::min());
                }
                maxi = maxi<longPath[ii][jj]?longPath[ii][jj]:maxi;
            }
        }
        return maxi;
    }
};