Standard C++ dfs


  • 0
    U
    class Solution {
    public:
        int helper(vector<vector<int>>& matrix, int sx, int sy,vector<vector<int>>&visited)
        {
            if(visited[sx][sy] != -1)return visited[sx][sy];
            
            int a1,a2,a3,a4;
            a1 = (sx > 0 && matrix[sx-1][sy] > matrix[sx][sy])?1 + helper(matrix,sx-1,sy,visited):0;
            a2 = (sy > 0 && matrix[sx][sy-1] > matrix[sx][sy])?1 + helper(matrix,sx,sy-1,visited):0;
            a3 = (sx < matrix.size()-1 && matrix[sx+1][sy] > matrix[sx][sy])?1 + helper(matrix,sx+1,sy,visited):0;
            a4 = (sy < matrix[0].size()-1 && matrix[sx][sy+1] > matrix[sx][sy])?1 + helper(matrix,sx,sy+1,visited):0;
     
            visited[sx][sy] = max(1,max(a1,max(a2,max(a3,a4))));
            return visited[sx][sy];
        }
        
        int longestIncreasingPath(vector<vector<int>>& matrix) {
            if(matrix.empty())return 0;
            int maxPath = 1;
            vector<vector<int>>visited(matrix.size(), vector<int>(matrix[0].size(),-1));
            for(int i=0; i<matrix.size(); i++)
            {
                for(int j=0; j<matrix[0].size(); j++)
                {
                    maxPath = max(maxPath,helper(matrix,i,j,visited));
                }
            }
            return maxPath;
        }
    };

Log in to reply
 

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