C++, 60ms, DFS solution


  • 0

    The key of the problem is to save intermediate results.

    class Solution {
    public:
    int check(vector<vector<int>>& matrix,vector<vector<int>>& res,int rsz, int csz, int i,int j){
        if (res[i][j]>0) return res[i][j];   //already checked, just return the value
        int curLen = 1;
        if (i>0 && matrix[i-1][j]>matrix[i][j]) 
            curLen=max(curLen,1+check(matrix,res,rsz,csz,i-1,j));
        if (i<rsz-1 && matrix[i+1][j]>matrix[i][j]) 
            curLen=max(curLen,1+check(matrix,res,rsz,csz,i+1,j));
        if (j>0 && matrix[i][j-1]>matrix[i][j]) 
            curLen=max(curLen,1+check(matrix,res,rsz,csz,i,j-1));
        if (j<csz-1 && matrix[i][j+1]>matrix[i][j]) 
            curLen=max(curLen,1+check(matrix,res,rsz,csz,i,j+1));
        res[i][j]=curLen;
        return curLen;
    }
    
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if (matrix.empty()||matrix[0].empty()) return 0;
        int rsz = matrix.size();
        int csz = matrix[0].size();
        vector<vector<int>> res(rsz,vector<int> (csz,-1));
        int maxLen = 1,curLen;
        for (int i=0;i<rsz;i++)
        for (int j=0;j<csz;j++){
            curLen = check(matrix,res,rsz,csz,i,j);
            maxLen = max(maxLen,curLen);
        }
        return maxLen;
    }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.