C++ Solution using dfs + memorization should be easy to understand


  • 0
    Y
    class Solution {
    public:
        int longestIncreasingPath(vector<vector<int>>& matrix) {
            int ans = 0;
            if(!matrix.size())
                return ans;
            int n = matrix.size(), m = matrix[0].size();
            vector<vector<int>> dp(n, vector<int>(m, 0));
            init(dp);
            for(int i = 0; i < n; ++ i){
                for(int j = 0; j < m; ++ j){
                    if(!dp[i][j]){
                        dfs(i, j, dp, matrix, ans, true);
                    }
                }
            }
            init(dp);
            for(int i = 0; i < n; ++ i){
                for(int j = 0; j < m; ++ j){
                    if(!dp[i][j]){
                        dfs(i, j, dp, matrix, ans, false);
                    }
                }
            }
            
            return ans;
        }
    private:
        void dfs(int r, int c, vector<vector<int>> &dp, vector<vector<int>>& matrix, int &ans, bool isdec){
            int n = dp.size(), m = dp[0].size();
            for(int i = 0; i < 4; ++ i){
                int nr = r + dir[i][0], nc = c + dir[i][1];
                if(nr >= 0 && nr < n && nc >= 0 && nc < m ){
                    if(isdec){
                        if(matrix[r][c] > matrix[nr][nc]){
                            if(!dp[nr][nc]){
                                dfs(nr, nc, dp, matrix, ans, isdec);
                            }
                            dp[r][c] = max(dp[r][c], dp[nr][nc]);
                        }
                    }else{
                        if(matrix[r][c] < matrix[nr][nc]){
                            if(!dp[nr][nc]){
                                dfs(nr, nc, dp, matrix, ans, isdec);
                            }
                            dp[r][c] = max(dp[r][c], dp[nr][nc]);
                        }
                    }
                }
            }
            ++ dp[r][c];
            ans = max(dp[r][c], ans);
        }
    
        void init(vector<vector<int>> &dp){
            for(int i = 0; i < dp.size(); ++ i){
                for(int j = 0; j < dp[0].size(); ++ j){
                    dp[i][j] = 0;
                }
            }
        }
    private:
    int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
    };

Log in to reply
 

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