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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * @author Senky
 * @date 2023.08.24
 * @par url https://www.nowcoder.com/creation/manager/content/584337070?type=column&status=-1
 * @param matrix int整型二维数组 描述矩阵的每个数
 * @param matrixRowLen int matrix数组行数
 * @param matrixColLen int* matrix数组列数
 * @return int整型
 */
#include <math.h>
#include <stdlib.h>
int DFS(int** matrix, int matrixRowLen, int* matrixColLen, int row, int column, int **dp)
{

    if(dp[row][column] != 0)
    {
        return dp[row][column];
    }

    int direction[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};/*上,下,左,右*/
    int max_len = 1;/*最大长度，初始化为1*/

    for(int d = 0; d < 4; d++)
    {
        int new_i = row + direction[d][0];
        int new_j = column + direction[d][1];

        if (new_i >= 0 && new_i < matrixRowLen && new_j >= 0 && new_j < matrixColLen[new_i] && matrix[row][column] < matrix[new_i][new_j]) 
        {
            int path_len = 1 + DFS(matrix, matrixRowLen, matrixColLen, new_i, new_j, dp);
            max_len = fmax(max_len, path_len);
        }
    }
    
    dp[row][column] = max_len;
    
    return max_len;
}

int solve(int** matrix, int matrixRowLen, int* matrixColLen ) 
{
    // write code here
    if(matrix == NULL || matrixRowLen == 0 || *matrixColLen == 0)
    {
        return 0;
    }

    int max_path_len = 0;/*最大路径长度*/
    int ** dp = (int**)malloc(matrixRowLen * sizeof(int*));/*dp数组，大小同等于matrix*/

    for(int i = 0; i < matrixRowLen; i++)
    {
        dp[i] = (int*)calloc(matrixColLen[i], sizeof(int)); /*初始化为0*/
    }
    
    for(int i = 0; i < matrixRowLen; i++)
    {
        for(int j = 0; j < matrixColLen[i]; j++)
        {
            /*遍历每一个元素，将每一个元素作为起点时的路径长度返回*/
            int path_len = DFS(matrix, matrixRowLen, matrixColLen, i , j, dp);

            /*每次都只记录最大的那个路径长度*/
            max_path_len = fmax(max_path_len, path_len);
        }
    }

    for (int i = 0; i < matrixRowLen; i++) 
    {
        free(dp[i]);
    }
    free(dp);
    
    return max_path_len;

}