[RainbowSecret] clean C++ implementation with detailed explanation


  • 4

    At first, I use the bool-flag-array to record whether the position (i,j) has been visited. But when visited before, I should return the recorded value. When not, I should calculate the 4-direction-value and set the max value to be the value and add 1 to get the result.

    Also, we can update the max-value when DFS .

    class Solution {
    public:
        int longestIncreasingPath(vector<vector<int>>& matrix) {
            int result=INT_MIN;
            int m=matrix.size();
            if(m==0)  return 0;
            int n=matrix[0].size();
            vector<vector<int>> state(m, vector<int>(n, 0));
            for(int i=0; i<m; i++){
                for(int j=0; j<n; j++){
                    if(state[i][j]==0)
                        dfs(i,j,matrix,state,result);
                }
            }
            return result;
        }
        
        /*** return the max-len-start-from-cur-position-i-j ***/
        int dfs(int i, int j, vector<vector<int>>& matrix, vector<vector<int>>& state, int& result){
            if(state[i][j]!=0)  return state[i][j];
            
            int len1=0, len2=0, len3=0, len4=0;
            /*** only-move-forward-when-next-step-value-satisfy-the-condition ***/
            if(i+1<state.size()  &&  matrix[i+1][j]>matrix[i][j])  
                len1=dfs(i+1, j, matrix, state, result);
            if(i-1>=0  &&  matrix[i-1][j]>matrix[i][j])  
                len2=dfs(i-1, j, matrix, state, result);
            if(j+1<state[0].size()  &&  matrix[i][j+1]>matrix[i][j])  
                len3=dfs(i, j+1, matrix, state, result);
            if(j-1>=0  &&  matrix[i][j-1]>matrix[i][j])  
                len4=dfs(i, j-1, matrix, state, result);
            /*** get-the-max-value-start-from-i-j ***/    
            state[i][j] =  max(max(max(len1, len2), len3), len4);
            state[i][j]++;
            /*** update-the-final-value ***/
            result=max(result, state[i][j]);
            return state[i][j];
        }
    };

  • 1

    In fact , the posted solution is really dirty .... Here is a much better coding style implementation ...

    class Solution {
        const vector<vector<int>> move = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    public:
        int longestIncreasingPath(vector<vector<int>>& matrix) {
            if(matrix.size()==0) return 0;
            int m = matrix.size(), n = matrix[0].size();
            vector<vector<int>> cache(m, vector<int>(n, 0));
            int result = 1;
            for(int i = 0; i < m; i++){
                for(int j = 0; j < n; j++){
                    int len = dfs(matrix, i, j, m, n, cache);
                    result = max(result, len);
                }
            }
            return result;
        }
        
        int dfs(vector<vector<int>>& matrix, int i, int j, int m, int n, vector<vector<int>>& cache){
            if(cache[i][j] != 0)  return cache[i][j];
            int result = 1;
            for(auto dir : move) {
                int x = i + dir[0], y = j + dir[1];
                if(x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] <= matrix[i][j])  continue;
                int len = 1 + dfs(matrix, x, y, m, n, cache);
                result = max(result, len);
            }
            cache[i][j] = result;
            return result;
        }
    };

Log in to reply
 

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