解题思路

从任意一个方格出发，每次只能走到相邻（上下左右）而且数字更大的方格，问所有合法路径中数字和最大是多少。

因为只能往数字更大的格子走，路径永远不会绕成圈，所以这是一张有向无环图，可以用记忆化深搜。

思路：

1. 先按题目给的算法生成 n 行 m 列的矩阵：
   • 从 s 开始，每次计算 s = (s × 345) mod 19997
   • 当前方格的数字就是 (s mod 10) + 1
2. 定义 f[x][y] 表示从 (x,y) 出发能得到的最大数字和
3. 用深搜计算 f[x][y]：
   • 先看上下左右四个方向
   • 如果邻居没出界、而且数字比当前格子更大，就递归求它的 f
   • 取四个方向里最大的那个作为下一步
   • 所以 f[x][y] = 当前格子的数字 + 四个方向中最大的 f
4. 因为可以从任意格子出发，所以最后把所有格子都试一遍，答案就是最大的 f

为什么要记忆化？ 同一个格子可能被很多条路径经过，如果每次重新深搜会超时。算过一次就把 f 存起来，下次直接用，每个格子最多算一次。

举例：样例 1 中 4 行 5 列，最大路径是 4 + 5 + 7 + 8 = 24，这正是题目给的答案。

参考代码

#include <iostream>
using namespace std;

int n, m;              // 方格矩阵有 n 行 m 列
int a[105][105];       // a[i][j] 存每个方格里的数字
int f[105][105];       // f[i][j] 存从 (i,j) 出发能得到的最大数字和
int dx[4] = {-1, 1, 0, 0};  // 上、下、左、右的行变化
int dy[4] = {0, 0, -1, 1};  // 上、下、左、右的列变化

// 深搜：求从 (x,y) 出发能得到的最大数字和
int dfs(int x, int y) {
    // 这个格子已经算过了，直接用结果（记忆化，避免重复算）
    if (f[x][y] > 0) return f[x][y];

    int best = 0;  // 下一步能加的最大数字和，先假设一步都走不了
    // 尝试走上、下、左、右四个方向
    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k];  // 下一个格子的行
        int ny = y + dy[k];  // 下一个格子的列
        // 没出界，而且下一个格子的数字必须更大，才能走
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m
            && a[nx][ny] > a[x][y]) {
            int t = dfs(nx, ny);  // 从那个格子出发能得到的最大和
            if (t > best) best = t;  // 取四个方向里最大的
        }
    }
    // 当前格子的数字 + 后面能加的最大数字和
    f[x][y] = a[x][y] + best;
    return f[x][y];
}

int main() {
    int s;  // 数据生成器的初始数值
    cin >> n >> m >> s;
    // 按题目给的算法依次生成每个方格的数字
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            s = (s * 345) % 19997;
            a[i][j] = (s % 10) + 1;
        }
    }

    int maxn = 0;  // 记录所有路径中的最大数字和
    // 可以从任意一个方格出发，所以每个格子都试一遍
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int t = dfs(i, j);  // 从 (i,j) 出发的最大数字和
            if (t > maxn) maxn = t;  // 更新最大值
        }
    }
    cout << maxn;  // 输出答案
    return 0;
}

复杂度分析

• 时间复杂度：O(n×m)，每个格子最多被计算一次
• 空间复杂度：O(n×m)，存矩阵和每个格子的结果