方格取数
题目描述
在 n 行、m 列的方格矩阵中，每个方格都包含一个数字。小明可以从任意方格出发开始移动。每次移动可以移到与当前方格有一条边相邻的方格(即向上、下、左或右方向移动 1 格，且不能移出边界)。除此之外，你移动到的方格中的数字必须比当前方格中的数字更大。
请你帮助小明编程规划移动路径，使路径上经过的所有数字之和最大。
本题方格中的数据根据输入的初始数字 s 按照如下算法生成:
for i = 1, 2, ... n
for j = 1, 2, ... m
s ← (s × 345) mod 19997
矩阵第 i 行第 j 列方格中的数字为(s mod 10) + 1
请你帮助小明编程规划移动路径，使路径上经过的所有数字之和最大。
本题方格中的数据根据输入的初始数字 s 按照如下算法生成:
for i = 1, 2, ... n
for j = 1, 2, ... m
s ← (s × 345) mod 19997
矩阵第 i 行第 j 列方格中的数字为(s mod 10) + 1
输入
正整数 n, m (方格的大小), s (数据生成器的初始数值)。1 ≤ n,m ≤ 100，1 ≤ s ≤ 19,997。
输出
所有合法路径中的最大数字和。
样例
输入：
4 5 97
输出：
24
输入：
40 50 1
输出：
47
说明
样例1输入4 5 97，就会产生如下图所示的矩阵，那么所有合法路径中最大数字和为：4 + 5 + 7 + 8 = 24。
[quote]
9 7 10 10 8
2 9 2 5 3
2 5 5 7 7
5 8 4 8 5
[/quote]
[quote]
9 7 10 10 8
2 9 2 5 3
2 5 5 7 7
5 8 4 8 5
[/quote]