Share my C code using DFS.


  • 1
    W
    void maxlength(int** matrix, int** length, int i, int j, int matrixRowSize, int matrixColSize) 
    {
    int len = 0;
    if (i > 0 && matrix[i-1][j] < matrix[i][j]) {
        if (length[i-1][j] == 0)    maxlength(matrix, length, i-1, j, matrixRowSize, matrixColSize);
        len = len > length[i-1][j] ? len : length[i-1][j];
    }
    if (i < matrixRowSize-1 && matrix[i+1][j] < matrix[i][j]) {
        if (length[i+1][j] == 0)    maxlength(matrix, length, i+1, j, matrixRowSize, matrixColSize);
        len = len > length[i+1][j] ? len : length[i+1][j];
    }
    if (j > 0 && matrix[i][j-1] < matrix[i][j]) {
        if (length[i][j-1] == 0)    maxlength(matrix, length, i, j-1, matrixRowSize, matrixColSize);
        len = len > length[i][j-1] ? len : length[i][j-1];
    }
    if (j < matrixColSize-1 && matrix[i][j+1] < matrix[i][j]) {
        if (length[i][j+1] == 0)    maxlength(matrix, length, i, j+1, matrixRowSize, matrixColSize);
        len = len > length[i][j+1] ? len : length[i][j+1];
    }
    
    length[i][j] = len + 1;
    return;
    }
    
    int longestIncreasingPath(int** matrix, int matrixRowSize, int matrixColSize) {
    if (matrixRowSize == 0 || matrixColSize == 0) return 0;
    
    int max = 1, i, j;
    int** length = (int**)malloc(sizeof(int*)*matrixRowSize);
    for (i = 0; i < matrixRowSize; i++)
        length[i] = (int*)calloc(matrixColSize, sizeof(int));
    
    for (i = 0; i < matrixRowSize; i++) {
        for (j = 0; j < matrixColSize; j++) {
            if (length[i][j] == 0) maxlength(matrix, length, i, j, matrixRowSize, matrixColSize);
            
            if (max < length[i][j]) max = length[i][j];
        }
    }
    
    for (i = 0; i < matrixRowSize; i++) free(length[i]);
    free(length);
    
    return max;
    }

Log in to reply
 

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