AT_abc358_g [ABC358G] AtCoder Tour

题目描述

AtCoder Land 由 $H$ 行 $W$ 列的网格组成。从上往下第 $i$ 行，从左往右第 $j$ 列的格子记作 $(i, j)$。

高桥君一开始在格子 $(S_i, S_j)$，他会重复进行 $K$ 次如下操作：

• 高桥君可以选择留在当前位置，或者移动到相邻的格子。之后，他会获得当前所在格子的 $A_{i, j}$ 的乐趣值。

请你求出高桥君能够获得的乐趣值总和的最大值。

这里，相邻的格子指的是满足 $|x - x'| + |y - y'| = 1$ 的格子 $(x', y')$。

输入格式

输入按以下格式从标准输入给出。

$H$ $W$ $K$ $S_i$ $S_j$ $A_{1, 1}$ $A_{1, 2}$ $\ldots$ $A_{1, W}$ $A_{2, 1}$ $A_{2, 2}$ $\ldots$ $A_{2, W}$ $\vdots$ $A_{H, 1}$ $A_{H, 2}$ $\ldots$ $A_{H, W}$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

2 3 3
1 2
2 1 2
3 4 5

输出 #1

14

输入输出样例 #2

输入 #2

2 2 1000000000
2 1
100 100
100 99

输出 #2

100000000000

说明/提示

限制条件

• $1 \leq H, W \leq 50$
• $1 \leq K \leq 10^9$
• $1 \leq S_i \leq H$
• $1 \leq S_j \leq W$
• $1 \leq A_{i, j} \leq 10^9$
• 输入的所有值均为整数

样例解释 1

高桥君可以按如下方式行动，使乐趣值总和达到 $14$：

• 一开始，高桥君在 $(1, 2)$。
• 高桥君移动到格子 $(2, 2)$，获得 $A_{2, 2} = 4$ 的乐趣值。
• 高桥君移动到格子 $(2, 3)$，获得 $A_{2, 3} = 5$ 的乐趣值。
• 高桥君留在格子 $(2, 3)$，获得 $A_{2, 3} = 5$ 的乐趣值。

高桥君无法获得比 $14$ 更大的乐趣值，因此输出 $14$。

由 ChatGPT 4.1 翻译