{"problem":{"name":"[信息与未来 2016] 方格取数","description":{"content":"在 $n$ 行 $m$ 列的方格矩阵中，每个方格都包含一个数字。小明可以从任意方格出发开始移动。每次移动可以移到与当前方格有一条边相邻的方格（即向上、下、左或右方向移动 $1$ 格，且不能移出边界）。除此之外，你移动到的方格中的数字必须比当前方格中的数字更大。 请你帮助小明编程规划移动路径，使路径上经过的所有数字之和最大。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB4140"},"statements":[{"statement_type":"Markdown","content":"在 $n$ 行 $m$ 列的方格矩阵中，每个方格都包含一个数字。小明可以从任意方格出发开始移动。每次移动可以移到与当前方格有一条边相邻的方格（即向上、下、左或右方向移动 $1$ 格，且不能移出边界）。除此之外，你移动到的方格中的数字必须比当前方格中的数字更大。\n\n请你帮助小明编程规划移动路径，使路径上经过的所有数字之和最大。\n\n## Input\n\n一行三个正整数 $n,m,s$。\n\n本题方格 $a$ 中的数据根据输入的初始数字 $s$ 按照如下算法生成：\n\n$$\n\\begin{aligned}\n&\\text{for } i=1\\text{ to } n\\\\\n&\\quad\\text{for } j=1\\text{ to } m\\\\\n&\\qquad s\\gets(s\\times345) \\bmod 19997\\\\\n&\\qquad a_{i,j}\\gets (s\\bmod 10)+1\\\\\n&\\quad \\text{end for}\\\\\n&\\text{end for}\n\\end{aligned}\n$$\n\n## Output\n\n所有合法路径中的最大数字和。\n\n[samples]\n\n## Note\n\n### 样例 $\\textbf 1$ 解释\n样例数据 1 对应的矩阵如下。图中路径数字之和 $4+5+7+8=24$。\n$$\n\\begin{array}{|c|c|c|c|c|}\\hline \n9 & 7 & 10 & 10 & 8\\\\\\hline\n2 & 9 & 2 & 5 &3\\\\\\hline\n2 & 5 & \\red5 & \\red7 & 7\\\\\\hline\n5 & 8 & \\red4 & \\red8 & 5\\\\\\hline\n\\end{array}\n$$\n### 数据范围\n$1\\le n,m\\le 100,1\\le s\\le 19997$。\n> 本题原始满分为 $20\\text{pts}$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGB4140","tags":["搜索","2016","江苏","枚举","信息与未来"],"sample_group":[["4 5 97","24"],["40 50 1","47"]],"created_at":"2026-03-03 11:09:25"}}