P1004（C语言代码）

解题思路:
最开始使用的dfs加visited数组，对于100*99的数组直接超时了。

参考https://blog.dotcpp.com/a/70053修改后，正确提交，通过一个二维数组记录每个点为起点的最大滑雪长度。

超时代码:

#include <stdio.h>
#include <stdlib.h>

int directions[4][2] = {{0,  1},
                        {0,  -1},
                        {1,  0},
                        {-1, 0}};

void
dfs(int **data, int row, int col, int **visited, int path, int *maxsize, int from_x, int from_y) {
    int to_x, to_y;
    int cnt = 0;
    for (int i = 0; i < 4; i++) {
        to_x = from_x + directions[i][0];
        to_y = from_y + directions[i][1];
        if ((to_x >= 0 && to_x < row && to_y >= 0 && to_y < col) &&
            (data[to_x][to_y] < data[from_x][from_y]) &&
            (!visited[to_x][to_y])) {
            cnt++;
            visited[to_x][to_y] = 1;
            dfs(data, row, col, visited, path + 1, maxsize, to_x, to_y);
            visited[to_x][to_y] = 0;
        }
    }
    if (cnt == 0 && path > *maxsize) {      // 无路可走
        *maxsize = path;
    }
}

int main() {
    int row, col;
    scanf("%d %d", &row, &col);
    int **data = (int **) malloc(sizeof(int *) * row);
    int **visited = (int **) malloc(sizeof(int *) * row);
    for (int i = 0; i < row; i++) {
        data[i] = (int *) malloc(sizeof(int) * col);
        visited[i] = (int *) malloc(sizeof(int) * col);
        for (int j = 0; j < col; j++) {
            scanf("%d", &data[i][j]);
            visited[i][j] = 0;
        }
    }
    int maxsize = 0;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            visited[i][j] = 1;
            dfs(data, row, col, visited, 1, &maxsize, i, j);
            visited[i][j] = 0;
        }
    }
    printf("%d", maxsize);
    return 0;
}

参考代码:

#include #include #define MAX(a, b)((a)>(b)?(a):(b))
int directions[4][2] = {{0,  1},
                        {0,  -1},
                        {1,  0},
                        {-1, 0}};

int dfs(int **data, int row, int col, int **dp, int from_x, int from_y) {
    int to_x, to_y;
    int path = 0;
    for (int i = 0; i < 4; i++) {       // 4个方向
        to_x = from_x + directions[i][0];
        to_y = from_y + directions[i][1];
        if ((to_x >= 0 && to_x < row && to_y >= 0 && to_y < col) &&     // 目标点索引在范围内
            (data[to_x][to_y] < data[from_x][from_y])) {        // 下坡
            if (dp[to_x][to_y] == 0) {
                dfs(data, row, col, dp, to_x, to_y);        // 目标点未计算
            }
            path = MAX(path, dp[to_x][to_y]);       // 求出四个方向的最大距离
        }
    }
    return dp[from_x][from_y] = path + 1;
}

int main() {
    int row, col;
    scanf("%d %d", &row, &col);
    int **data = (int **) malloc(sizeof(int *) * row);
    int **dp = (int **) malloc(sizeof(int *) * row);
    for (int i = 0; i < row; i++) {
        data[i] = (int *) malloc(sizeof(int) * col);
        dp[i] = (int *) malloc(sizeof(int) * col);
        for (int j = 0; j < col; j++) {
            scanf("%d", &data[i][j]);
            dp[i][j] = 0;
        }
    }
    int maxsize = 0;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            maxsize = MAX(maxsize, dfs(data, row, col, dp, i, j));
        }
    }
    for (int i = 0; i < row; i++) {
        free(data[i]);
        free(dp[i]);
    }
    free(data);
    free(dp);
    printf("%d", maxsize);
    return 0;
}