poj1088滑雪问题

ゝ一世哀愁。 2022-06-18 08:38 208阅读 0赞

#include <stdio.h>  
      
    int matrix[100][100];  
    int dp[100][100];  
    int R;  
    int C;  
      
    int Max (int a, int b, int c, int d){
          
        int max1 = (a > b) ? a : b;  
        int max2 = (c > d) ? c : d;  
        return (max1 > max2) ? max1 : max2;  
    }  
      
    // dp[i][j] = max(dp[i-1][j], dp[i+1][j], dp[i][j-1], dp[i][j+1]) + 1  
    int MaxLength(int i, int j){
          
        if (dp[i][j] > 0)  
            return dp[i][j];  
        int a = 0;  
        int b = 0;  
        int c = 0;  
        int d = 0;  
        if (i-1 >= 0 && matrix[i][j] > matrix[i-1][j]){
          
            a = MaxLength (i-1, j);  
        }  
        if (i+1 < R && matrix[i][j] > matrix[i+1][j]){
          
            b = MaxLength (i+1, j);  
        }  
        if (j-1 >= 0 && matrix[i][j] > matrix[i][j-1]){
          
            c = MaxLength (i, j-1);  
        }  
        if (j+1 < C && matrix[i][j] > matrix[i][j+1]){
          
            d = MaxLength (i, j+1);  
        }  
        return dp[i][j] = Max (a, b, c, d) + 1;  
    }  
      
    int main(void){
          
        int i, j;  
        int max;  
      
        while (scanf ("%d%d", &R, &C) != EOF){
          
            for (i=0; i<R; ++i)  
                for (j=0; j<C; ++j){
          
                    scanf ("%d", &matrix[i][j]);  
                    dp[i][j] = 0;  
                }  
            for (i=0; i<R; ++i){
          
                for (j=0; j<C; ++j){
          
                    MaxLength (i, j);  
                }  
            }  
            max = 0;  
            for (i=0; i<R; ++i){
          
                for (j=0; j<C; ++j){
          
                    if (max < dp[i][j]){
          
                        max = dp[i][j];  
                    }  
                }  
            }  
            printf ("%d\n", max);  
        }  
      
        return 0;  
    }