方格取数

方格取数

题目描述
在 nn 行、mm 列的方格矩阵中,每个方格都包含一个数字。

小明可以从任意方格出发开始移动。每次移动可以移到与当前方格有一条边相邻的方格(即向上、下、左或右方向移动 11 格,且不能移出边界)。除此之外,你移动到的方格中的数字必须比当前方格中的数字更大。

请你帮助小明编程规划移动路径,使路径上经过的所有数字之和最大。
本题方格中的数据根据输入的初始数字 ss 按照如下算法生成:

for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
s = (s * 345) % 19997;
a[i][j] = s + 1;
}
}
矩阵第 ii 行第 jj 列方格中的数字为s + 1s+1

输入
正整数 n, mn,m (方格的大小), ss (数据生成器的初始数值)。

输出
所有合法路径中的最大数字和。

输入1
4 5 97
输入2
40 50 1
输出1
58297
输出2
151670
提示
样例数据11对应的矩阵如下。

13469 7157 9190 10680 4808
18662 19009 18742 6615 2173
9452 1085 14035 2457 7447
9255 13108 2594 14718 18125
数据规模
对于50%的数据1 \leq n,m \leq 500

对于全部的数据1 \leq n,m \leq 2000,1 \leq s \leq 199971≤n,m≤2000,1≤s≤19997

信息

ID
1113
难度
9
分类
搜索 | 记忆化搜索 点击显示
标签
递交数
9
已通过
1
通过率
11%
被复制
1
上传者