AcWing 901. 滑雪
宋标 Lv5
  2022-08-18 02:31:11 2022-08-18 02:31    

题目

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

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

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

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

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

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

在给定矩阵中，一条可行的滑行轨迹为 。

在给定矩阵中，最长的滑行轨迹为 ，沿途共经过 个区域。

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

输入格式

第一行包含两个整数 和 。

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

输出格式

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

数据范围

,
矩阵中整数

输入样例：

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

题解

直接dfs会超时

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
39
40
41
42
43
44
45
#include <iostream>
#include <cstring>
#include <algorithm>
#define N 310

using namespace std;

int g[N][N], f[N][N]; // f[i, j] 表示i行j列的滑雪路径，属性是最远距离
int n, m;
int xy[][4] = {{1, 0, -1, 0}, {0, 1, 0, -1}};

int dfs(int x, int y)
{
    int &v = f[x][y];
    // 只要当前x行y列的路径已经求过，则返回
    if (~v) return v;
    // 初始值1
    v = 1;
    for (int i = 0; i < 4; ++ i)
    {
        int a = x + xy[0][i], b = y + xy[1][i];
        if (a >= 0 && a <n && b >= 0 && b < m && g[x][y] > g[a][b])
            // dfs(a, b) + 1 表示当前的位置到下一个位置的路径
            v = max(v, dfs(a, b) + 1);
    }
    return v;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; ++ i)
        for (int j = 0; j < m; ++ j)
            scanf("%d", &g[i][j]);

    memset(f, -1, sizeof f);

    int ans = 0;
    for (int i = 0; i < n; ++ i)
        for (int j = 0; j < m; ++ j)
            ans = max(ans, dfs(i, j));

    cout << ans << endl; 
    return 0;
}
 评论