Longest_Increasing.png

/**
* DFS along will not do; it has to be seasoned with some pruning...
*/
int dfs(int **matrix, int m, int n, bool **flags, int i, int j, int **max) {
    int up = 0, right = 0, down = 0, left = 0, len = 0;
    if (i - 1 >= 0 && !flags[i - 1][j] && matrix[i - 1][j] > matrix[i][j] && max[i - 1][j] < max[i][j] + 1) {
        max[i - 1][j] = max[i][j] + 1;
        flags[i - 1][j] = true;
        up = 1 + dfs(matrix, m, n, flags, i - 1, j, max);
        flags[i - 1][j] = false;
    }
    if (len < up) { len = up; }

    if (j + 1 < n && !flags[i][j + 1] && matrix[i][j + 1] > matrix[i][j] && max[i][j + 1] < max[i][j] + 1) {
        if (max[i][j + 1] < max[i][j] + 1) { max[i][j + 1] = max[i][j] + 1; }
        flags[i][j + 1] = true;
        right = 1 + dfs(matrix, m, n, flags, i, j + 1, max);
        flags[i][j + 1] = false;
    }
    if (len < right) { len = right; }

    if (i + 1 < m && !flags[i + 1][j] && matrix[i + 1][j] > matrix[i][j] && max[i + 1][j] < max[i][j] + 1) {
        if (max[i + 1][j] < max[i][j] + 1) { max[i + 1][j] = max[i][j] + 1; }
        flags[i + 1][j] = true;
        down = 1 + dfs(matrix, m, n, flags, i + 1, j, max);
        flags[i + 1][j] = false;
    }
    if (len < down) { len = down; }

    if (j - 1 >= 0 && !flags[i][j - 1] && matrix[i][j - 1] > matrix[i][j] && max[i][j - 1] < max[i][j] + 1) {
        if (max[i][j - 1] < max[i][j] + 1) { max[i][j - 1] = max[i][j] + 1; }
        flags[i][j - 1] = true;
        left = 1 + dfs(matrix, m, n, flags, i, j - 1, max);
        flags[i][j - 1] = false;
    }
    if (len < left) { len = left; }

    return len;
}

int longestIncreasingPath(int** matrix, int matrixSize, int* matrixColSize) {
    bool **flags = (bool**)malloc(matrixSize * sizeof(*flags));
    int **max = (int**)malloc(matrixSize * sizeof(*max));
    for (int i = 0; i < matrixSize; i++) {
        flags[i] = (bool*)malloc(*matrixColSize * sizeof(bool));
        max[i] = (int*)malloc(*matrixColSize * sizeof(int));
        for (int j = 0; j < *matrixColSize; j++) { 
            flags[i][j] = false; 
            max[i][j] = INT_MIN;
        }
    }

    int len = 0;
    for (int i = 0; i < matrixSize; i++) {
        for (int j = 0; j < *matrixColSize; j++) {
            if (max[i][j] < 1) {
                max[i][j] = 1; 
                flags[i][j] = true;
                int tlen = dfs(matrix, matrixSize, *matrixColSize, flags, i, j, max);
                flags[i][j] = false;
                if (len < tlen) { len = tlen; }
            }
        }
    }
    return len + 1;
}