题解

题面描述

给定一个由$m*n$ 个单元格组成的矩阵，每个单元格有一个高度值（范围为$1$到$2^{31}-1$）。你可以从任意单元格开始，向上下左右四个方向滑动，每次只能滑向高度严格更低的相邻单元格，且不能重复访问已走过的格子。求满足规则的最长滑行路径长度。

思路

1. 定义状态： 用二维数组 dp[i][j] 表示以格子$(i,j)$ 为起点，能够滑行的最长路径长度。

2. 状态转移： 对于格子$(i,j)$，向四个方向探索相邻格子$(x,y)$，若高度满足 ${height}[x][y]$ <${height}[i][j]$ 则 $dp[i][j]=max(dp[i][j],1 + dp[x][y])$

3. 计算顺序： 由于状态转移依赖于“更低高度”的格子，我们可以按照高度从低到高的顺序来计算 dp。具体做法是先将所有格子按高度排序（或桶排序、基数排序），然后依次更新其四周更高格子的 dp。当然，也可以直接对每个格子做带记忆化的深度优先搜索（DFS + 记忆化），时间复杂度均为$O(mn)$。

4. 结果： 最终答案为 $max_{0\le i<m,\;0\le j<n}dp[i][j]$

C++

#include <bits/stdc++.h>
using namespace std;

int m, n;
vector<vector<int>> matrix;
vector<vector<int>> dp;
// 四个方向：上、下、左、右
int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};

// 从 (i,j) 出发的最长路径
int dfs(int i, int j) {
    if (dp[i][j] != 0) return dp[i][j];
    int best = 1; // 最少能滑行自己这格
    for (auto &d : dirs) {
        int x = i + d[0], y = j + d[1];
        if (x>=0 && x<m && y>=0 && y<n && matrix[x][y] < matrix[i][j]) {
            best = max(best, 1 + dfs(x, y));
        }
    }
    return dp[i][j] = best;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> m >> n;
    matrix.assign(m, vector<int>(n));
    dp.assign(m, vector<int>(n, 0));

    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            cin >> matrix[i][j];

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

    cout << ans << "\n";
    return 0;
}

Python

from functools import lru_cache
import sys
sys.setrecursionlimit(10**7)

# 读取输入
m, n = map(int, sys.stdin.readline().split())
matrix = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]

dirs = [(-1,0),(1,0),(0,-1),(0,1)]

@lru_cache(None)
def dfs(i, j):
    """返回以 (i,j) 为起点的最长滑雪路径长度"""
    best = 1
    for dx, dy in dirs:
        x, y = i + dx, j + dy
        if 0 <= x < m and 0 <= y < n and matrix[x][y] < matrix[i][j]:
            best = max(best, 1 + dfs(x, y))
    return best

# 计算结果
ans = max(dfs(i, j) for i in range(m) for j in range(n))
print(ans)

Java

import java.io.*;
import java.util.*;

public class Main {
    static int m, n;
    static int[][] matrix, dp;
    // 四个方向：上、下、左、右
    static int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());

        matrix = new int[m][n];
        dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                matrix[i][j] = Integer.parseInt(st.nextToken());
            }
        }

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

        System.out.println(ans);
    }

    static int dfs(int i, int j) {
        // 如果已计算过，直接返回
        if (dp[i][j] != 0) return dp[i][j];
        int best = 1; // 至少包含自己
        for (int[] d : dirs) {
            int x = i + d[0], y = j + d[1];
            if (x >= 0 && x < m && y >= 0 && y < n 
                && matrix[x][y] < matrix[i][j]) {
                best = Math.max(best, 1 + dfs(x, y));
            }
        }
        dp[i][j] = best;
        return best;
    }
}

题目内容

某手机应用市场下载量最高的游戏是《欢乐滑雪》游戏。

游戏会自动生成一张 $m*n$ 格子的地形图，每一个单元格，会标明格子的高度，格子的高度可能是从 $1$ 到 $2147483647（即0×7FFFFFFF）$ 中的一个整数。

玩家可以自行选择起点，从玩家指定的任意单元格开始移动，并控制角色往上、下、左、右四个方向滑动。角色无法斜着移动或跑出地图之外，曾经路过的单元格，也不能再重复走。

游戏规则要求，控制角色滑雪的时候，只能从高住低滑，下一步到达的格子的高度，必须小于上一步格子的高度，如果玩家找到在地图满足规则要求的可以滑行的最长路径，就可以过关。请尝试挑战一下吧。

$1<= m,n<= 500$

$1 <= matrix[i] [j]<= 2147483647（即0×7FFFFFFF）$

其中 $i$ 和 $j$ 代表了格子的位置在第 $i$ 行第 $j$ 列，$0<=1<=m-1,0<=j<= n-1$ 。

输入描述

第一行是地图的行数 $m$ 和列数 $n$ ，比如 $4$ $4$ ，值的范围 $[1,500]$ ；

接下来会出现 $m$ 行，每行 $n$ 个数字，每个数字的值的范围 $[1,2147483647]$

输出描述

找到满足条件的最长路径，输出路径的长度。

样例1

输入

3 3
9 8 7
6 6 6
6 6 6

输出

4

说明

在该 $3*3$ 的地图中，满足游戏规则要求的最长滑雪路径是 $9$ $8$ $7$ $6$ ，所以返回路径长度是 $4$ 。请注意，，到达 $6$ 后，不能再往高度为 $6$ 的格子滑。

样例2

输入

1 5
10 11 12 13 14

输出

5

说明

在该 $1*5$ 的地图中，满足游戏规则要求的最长滑雪路径是 $14$ $13$ $12$ $11$ $10$ ，所以返回路径长度是 $5$ 。