来源：AcWing

题目

给定一个R行C列的矩阵，表示一个矩形网格滑雪场。

矩阵中第 i 行第 j 列的点表示滑雪场的第 i 行第 j 列区域的高度。

一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。

当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。

下面给出一个矩阵作为例子：

1
2
3
4
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

在给定矩阵中，一条可行的滑行轨迹为24-17-2-1。

在给定矩阵中，最长的滑行轨迹为25-24-23-…-3-2-1，沿途共经过25个区域。

现在给定你一个二维矩阵表示滑雪场各区域的高度，请你找出在该滑雪场中能够完成的最长滑雪轨迹，并输出其长度(可经过最大区域数)。

输入格式

第一行包含两个整数R和C。

接下来R行，每行包含C个整数，表示完整的二维矩阵。

输出格式

输出一个整数，表示可完成的最长滑雪长度。

数据范围

1≤R,C≤300
0≤矩阵中整数≤10000

输入样例

1
2
3
4
5
6
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

输出样例：

1
25

分析

使用记忆化搜索，记录每个点的最大滑动长度

遍历每个点作为起点的情况，即状态表示为：f[i]j]表示从（i， j）开始滑动的路径，值为最大值

f[i][j]的状态计算可以分为4类，即上下左右四类，计算为上下左右的最大滑动距离 + 1：

f[i][j] = max(f[i - 1][j], f[i + 1][j], f[i][j - 1], f[i][j + 1]) + 1

那么问题就可以转化成计算上下左右的最大滑动距离，同时由于滑雪是必须滑到比当前低的点，所以不会存在一个点多次进入的问题，就可以使用递归来计算

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;

const int N = 310;

int n, m;
int h[N][N], f[N][N];	// h记录高度，f为状态计算

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 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 a = x + dx[i];
        int b = y + dy[i];
        if(a >= 0 && a < n && b >= 0 && b < m && h[a][b] < h[x][y])	// 边界条件
            f[x][y] = max(f[x][y], dp(a, b) + 1);
    }
    return f[x][y];
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            scanf("%d", &h[i][j]);
            
    memset(f, -1, sizeof f);
    
    int res = 0;
    for(int i = 0; i < n; i++)  
        for(int j = 0; j < m; j++)
            res = max(res, dp(i, j));
            
    printf("%d", res);
    return 0;
}