C语言求解滑雪问题

左手的ㄟ右手 2022-03-09 05:46 267阅读 0赞

**主要思路：**  
1.用一个全局二维数组存放用户输入的高度矩阵；  
2.定义一个二维数组visited\[ \]\[ \]初始化为0，用做访问矩阵，同时复用作该位置结点最长路径的记录矩阵；只要路径数据不为0，则说明该点已访问过了；  
3.对高度矩阵中的点逐个进行深度优先遍历，直至找出最长路径为止；  
4.注意深度优先遍历的递归结束条件为当前点已访问过或者当前点已越界。

/*---------------------------------------------------------------
    功能：求解滑雪问题
    描述：根据用户输入的一个高度矩阵，求解出最长的滑雪通道；
    首行输入高度矩阵的行数和列数，接着输入高度矩阵；
    滑雪道构成规则：当前点高度高于其上下左右某个高度时可形成滑雪道；
    输入示例：
    5 5
    1 2 3 4 5
    16 17 18 19 6
    15 24 25 20 7
    14 23 22 21 8
    13 12 11 10 9
    输出示例：
    25
    -----------------------------------------------------------------
    Author: Zhang Kaizhou
    Date: 2019-3-12 14:48:32
    -----------------------------------------------------------------*/
    #include <stdio.h>
    #include <stdlib.h>
    
    int m, n;
    int arr[110][110]; // 高度矩阵
    int visited[110][110] = { 0 }; // 访问记录数组,并记录从该点出发的最长路径，初始化为0
    int dir[2][4] = {
       {0, 0, -1, 1}, {-1, 1, 0, 0}}; // 四个搜索方向增量的定义
    
    int overstep_check(int i, int j);
    int longest_path(int i, int j);
    
    int main(){
        scanf("%d %d", &m, &n);
        int i, j, res = 0;
        for(i = 0; i < m; i++){ // 输入高度矩阵
            for(j = 0; j < n; j++){
                scanf("%d", &arr[i][j]);
            }
        }
        for(i = 0; i < m; i++){ // 逐点搜索判断其最长雪道
            for(j = 0; j < n; j++){
                res = res >= longest_path(i, j) ? res : longest_path(i, j);
            }
        }
        printf("%d\n", res);
    
        return 0;
    }
    
    int longest_path(int i, int j){ // 基于深度优先遍历的最长路径搜索
        int k, len;
        if(visited[i][j] != 0){
            return visited[i][j];
        }else{
            for(k = 0; k < 4; k++){
                if(overstep_check(i + dir[0][k], j + dir[1][k]) == 1){
                    if(arr[i][j] > arr[i + dir[0][k]][j + dir[1][k]]){ // 当前点高于其周围某个点时
                        len = longest_path(i + dir[0][k], j + dir[1][k]);
                        visited[i][j] = visited[i][j] > len ? visited[i][j] : len + (arr[i][j] - arr[i + dir[0][k]][j + dir[1][k]]); // 求出最长路径
                    }
                }
            }
            if(visited[i][j] == 0){ // 若当前点为高度矩阵中的最低点，则其最长路径即为自身高度
                visited[i][j] = arr[i][j];
            }
            return visited[i][j];
        }
    }
    
    int overstep_check(int i, int j){ // 判定坐标是否越界
       if(i >= 0 && i <= m && j >= 0 && j <= n){
            return 1;
       }else{
            return 0;
       }
    }