题解 | #矩阵最长递增路径#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 递增路径的最大长度
 * @param matrix int整型二维数组 描述矩阵的每个数
 * @param matrixRowLen int matrix数组行数
 * @param matrixColLen int* matrix数组列数
 * @return int整型
 */

#include <stdlib.h>
#define max(a, b) a > b ? a : b
int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

int dfs(int** matrix, int matrixRowLen, int* matrixColLen, int i, int j, int** dp) {
    if(dp[i][j] != 0) return dp[i][j];
    dp[i][j]++;
    for(int k = 0; k < 4; k++) {
        int nexti = i + dirs[k][0];
        int nextj = j + dirs[k][1];
        if(nexti >= 0 && nexti < matrixRowLen && nextj >= 0 && nextj < *matrixColLen && matrix[nexti][nextj] > matrix[i][j]) {
            dp[i][j] = max(dp[i][j], dfs(matrix, matrixRowLen, matrixColLen, nexti, nextj, dp) + 1);
        }
    }
    return dp[i][j];
}

int solve(int** matrix, int matrixRowLen, int* matrixColLen ) {
    // write code here
    if(matrixRowLen == 0) return 0;
    int** dp = (int**)malloc(sizeof(int*) * matrixRowLen);
    for(int i = 0; i < matrixRowLen; i++) {
        dp[i] = (int*)malloc(sizeof(int) * (*matrixColLen));
        for(int j = 0; j < *matrixColLen; j++) {
            dp[i][j] = 0;
        }
    }
    int res = 0;
    for(int i = 0; i < matrixRowLen; i++) {
        for(int j = 0; j < *matrixColLen; j++) {
            res = max(res, dfs(matrix, matrixRowLen, matrixColLen, i, j, dp));
        }
    }
    return res;

}