AtCoder Tour

题目描述

AtCoder Land 由一个有 $H$ 行 $W$ 列的网格表示。记 $(i, j)$ 为第 $i$ 行第 $j$ 列的格子。 Takahashi 从格子 $(S_i, S_j)$ 出发，重复以下动作 $K$ 次：

他可以选择停留在当前格子或移动到一个相邻格子。动作结束后，如果他在格子 $(i, j)$，他会获得欢乐值 $A_{i, j}$。

求他能获得的最大总欢乐值。 这里，只有当且仅当 $|x - x'| + |y - y'| = 1$ 时，格子 $(x', y')$ 被认为与格子 $(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}$

输出格式

输出答案。

2 3 3
1 2
2 1 2
3 4 5

14

2 2 1000000000
2 1
100 100
100 99

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$ 所有输入值都是整数。Takahashi 可以通过如下操作获得总欢乐值 $14$：

最初，他在 $(1, 2)$。 他移动到格子 $(2, 2)$。然后，他获得欢乐值 $A_{2, 2} = 4$。 他移动到格子 $(2, 3)$。然后，他获得欢乐值 $A_{2, 3} = 5$。 他停留在格子 $(2, 3)$。然后，他获得欢乐值 $A_{2, 3} = 5$。

他不能获得大于 $14$ 的总欢乐值，所以输出 $14$。

标签: AtCoder|abc358G

来源

AtCoder|abc358G