My c++ code using dfs


  • 0
    A
        int m, n;
        int DFS(vector<vector<int> >& matrix, vector<vector<int> >& his, int i, int j){
            int ans = 1;
            if(i+1 < m && matrix[i+1][j] > matrix[i][j]){
                if(his[i+1][j] == 0){
                    his[i+1][j] = DFS(matrix, his, i+1, j);
                }
                ans = max(ans, his[i+1][j]+1);
            }
            if(i-1 >= 0 && matrix[i-1][j] > matrix[i][j]){
                if(his[i-1][j] == 0){      
                    his[i-1][j] = DFS(matrix, his, i-1, j);
                }
                ans = max(ans, his[i-1][j]+1);
            }
            if(j-1 >= 0 && matrix[i][j-1] > matrix[i][j]){
                if(his[i][j-1] == 0){
                    his[i][j-1] = DFS(matrix, his, i, j-1);
                }
                ans = max(ans, his[i][j-1]+1);
            }
            if(j+1 < n && matrix[i][j+1] > matrix[i][j]){
                if(his[i][j+1] == 0){
                    his[i][j+1] = DFS(matrix, his, i, j+1);
                }
                ans = max(ans, his[i][j+1]+1);
            }
            return ans;
        }
        int longestIncreasingPath(vector<vector<int>>& matrix) {
            m = matrix.size();
            if(m == 0){
                return 0;
            }
            n = matrix[0].size();
            if(n == 0){
                return 0;
            }
            int ans = 0;
            vector<vector<int> >his;
            for(int i=0; i<m; i++){
                his.push_back(vector<int>(n, 0));
            }
            for(int i=0; i<m; i++){
                for(int j=0; j<n; j++){
                    if(his[i][j] == 0){
                        his[i][j] = DFS(matrix, his, i, j);
                        ans = max(his[i][j], ans);
                    }
                }
            }
            return ans;
        }
    

Log in to reply
 

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