Simple DFS solution


  • 0
    L
     int longestIncreasingPath(vector<vector<int>>& matrix) {
          
            if (matrix.empty())
                return 0;
                
            int N = matrix.size();
            int M = matrix[0].size();
        
            vector<vector<int>> lengths(N, vector<int>(M,1));
    
            int localmax = 0;
            for (int i = 0; i < N; ++i)
            {
                for (int j = 0; j < M; ++j)
                {
                    if (!lengths[i][j]==0)
                    {
                        localmax = max(localmax, dfs(matrix, lengths, i, j, N, M));
                    }
                }
            }
            
            return localmax;
        }
        
        int dfs(vector<vector<int>> & matrix, 
                 vector<vector<int>> & lengths, 
                 int i, int j, int N, int M)
        {
            if (lengths[i][j] > 1)
                return lengths[i][j];
                
            if (i+1 < N && matrix[i][j] > matrix[i+1][j])
            {
                lengths[i][j] = max(lengths[i][j], dfs(matrix, lengths, i+1, j, N, M)+1);
            }
            if (j+1 < M && matrix[i][j] > matrix[i][j+1])
            {
                lengths[i][j] = max(lengths[i][j], dfs(matrix, lengths, i, j+1, N, M)+1);
            }
            if (i-1 >= 0 && matrix[i][j] > matrix[i-1][j])
            {
                lengths[i][j] = max(lengths[i][j], dfs(matrix, lengths, i-1, j, N, M)+1);
            }
            if (j-1>= 0 && matrix[i][j] > matrix[i][j-1])
            {
                lengths[i][j] = max(lengths[i][j], dfs(matrix, lengths, i, j-1, N, M)+1);
            }
            return lengths[i][j];
        }
    

Log in to reply
 

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