C++_DFS_(Backtracking)_56ms_88.33%


  • 0

    At first I use the backtracking method and got the TLE result. The reason is that we have made lots of unnecessary compare and finding. For a certain factor matrix[i][j], we can use a vector to store the longest path which through this factor, on the other hand, this can also help us to avoid duplicate finding in this factor.

    Updated code (Accepted):

    class Solution {
    public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if(matrix.empty()) return 0;
    
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>> check(m,vector<int>(n,0));
        int res = 1;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                res = max(res, find(matrix, m, n, i, j, check));
            }
        }
        return res;
    }
    
    int find(vector<vector<int>>& matrix, int m, int n, int row, int col, vector<vector<int>>& check){
        int maxlen = check[row][col];
        if(check[row][col] > 0){return maxlen;}
        if(check[row][col]< INT_MAX){
            if(row > 0 && matrix[row - 1][col] > matrix[row][col]){maxlen = max(find(matrix, m, n, row - 1, col,check),maxlen);}//up
            if(row < m - 1 && matrix[row + 1][col] > matrix[row][col]){maxlen = max(find(matrix, m, n,  row + 1, col,check),maxlen);}//down
            if(col > 0 && matrix[row][col - 1] > matrix[row][col]){maxlen = max(find(matrix, m, n, row, col - 1,check),maxlen);}//left
            if(col < n - 1 && matrix[row][col + 1] > matrix[row][col]){maxlen = max(find(matrix, m, n, row, col + 1,check),maxlen);}//right
            check[row][col] = ++maxlen;
        }
        return maxlen;
    }
    };
    

    0_1475183590221_1FA0CD88-AEC5-4DEE-A55F-23F79E8A4B02.png


Log in to reply
 

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