My C++ DFS solution, store partial result


  • 0
    S
    class Solution {
    public:
    int dfs(vector<vector<int>>& matrix, vector<vector<int>>& visited, int i, int j, int m, int n) {
        int left, right, up, down;
        left = right = up = down = 0;
        
        if(i >= 1 && matrix[i-1][j] > matrix[i][j])
            up = visited[i-1][j] > 1 ? visited[i-1][j] : dfs(matrix, visited, i-1, j, m, n);
        
        if(j >= 1 && matrix[i][j-1] > matrix[i][j])
            left = visited[i][j-1] > 1 ? visited[i][j-1] : dfs(matrix, visited, i, j-1, m, n);
            
        if(i < m-1 && matrix[i+1][j] > matrix[i][j])
            down = visited[i+1][j] > 1 ? visited[i+1][j] : dfs(matrix, visited, i+1, j, m, n);
        
        if(j < n-1 && matrix[i][j+1] > matrix[i][j])
            right = visited[i][j+1] > 1 ? visited[i][j+1] : dfs(matrix, visited, i, j+1, m, n);
        
        visited[i][j] = 1 + max(max(up, down), max(left, right));
        
        return visited[i][j];
    }
    
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int m = matrix.size();
        if (m == 0) return 0;
        int n = matrix[0].size();
        vector<vector<int>> visited (m, vector<int>(n, 1));
        int result = 0;
        
        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                result = max(result, dfs(matrix, visited, i, j, m, n));
            }
        }
        return result;
    }
    

    };


Log in to reply
 

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