矩形滑雪场-记忆化搜索

解题思路:记忆化搜索

注意事项:

参考代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m, res;
int h[N][N],f[N][N],dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};
int dp(int x, int y){
    if (f[x][y]!= -1) return f[x][y];
    f[x][y] = 1;
    for (int i = 0; i < 4; i ++){
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 1 && nx <=n && ny >= 1 && ny <= m && h[nx][ny] < h[x][y]){
            f[x][y] = max(f[x][y], dp(nx,ny) + 1);
        }
    }
    return f[x][y];
}
int main(){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++){
        for (int j = 1; j <= m; j ++){
            scanf("%d", &h[i][j]);
        }
    }
    memset(f, -1, sizeof f);
    for (int i = 1; i <= n; i ++){
        for (int j = 1; j <=m ; j ++)
            res = max(res, dp(i,j));
    }
    printf("%d\n", res);
    return 0;
}