DP算法-滑雪

15 Sep 2024 in Algorithm Pageviews

dp

给定一个R 行 C 列的矩阵，表示一个矩形网格滑雪场。矩阵中第 i 行第 j 列的点表示滑雪场的第 i 行第 j 列区域的高度。

一个人从滑雪场的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。当然，一个人能够滑动到某相邻的前提是该区域的高度低于自己目前所在区域的高度。

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

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 ≤ 矩阵中整数 ≤ 1000

输入样例：

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

代码实现如下：

记忆化搜索

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 310;
vector<vector<int>> vis(N, vector<int>(N));
vector<vector<int>> a(N, vector<int>(N));
vector<vector<int>> f(N, vector<int>(N, -1));
vector<int> dir{-1, 0, 1, 0, -1};
int n = 0;
int m = 0;
int res = -1;

int dfs(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 x_ = x + dir[i];
        int y_ = y + dir[i + 1];
        if (x_ < 1 || x_ > n || y_ < 1 || y_ > m || a[x_][y_] >= a[x][y]) {
            continue;
        }
        f[x][y] = max(f[x][y], dfs(x_, y_) + 1);
    }
    res = max(res, f[x][y]);
    return f[x][y];
}

int main()
{
    cin >> n >> m;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dfs(i, j);
        }
    }
    cout << res << endl;
    return 0;
}