题目描述

Raven 先生被困在一个由 $N$ 行 $M$ 列组成的洞穴中，行从上到下编号为 $1$ 到 $N$，列从左到右编号为 $1$ 到 $M$。第 $i$ 行第 $j$ 列的格子记为 $(i, j)$。Raven 先生当前位于格子 $(S_R, S_C)$，洞穴的出口位于格子 $(T_R, T_C)$。

洞穴中的某些格子可能有障碍物。Raven 先生不能踏入有障碍物的格子。

某些格子可能有陷阱。Raven 先生第一次进入有陷阱的格子时，他必须消耗等于陷阱强度的能量点数。如果他的能量点数少于所需，则他无法进入该格子。

此外，某些格子可能有药水。Raven 先生第一次进入有药水的格子时，他会获得等于药水强度的能量点数。

Raven 先生初始有 $E$ 点能量。他可以在共享一条边（不仅仅是角）的格子之间移动。在出口格子上，如果他愿意，可以选择不离开洞穴而继续探索。请帮助他判断：如果可能到达出口，当他离开洞穴时能拥有的最大能量点数是多少？

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含七个整数 $N$、$M$、$E$、$S_R$、$S_C$、$T_R$ 和 $T_C$，含义如上所述。接下来的 $N$ 行中的第 $i$ 行描述了洞穴的第 $i$ 行。每行包含 $M$ 个整数 $V_{ij}$；其中第 $j$ 个整数表示第 $i$ 行第 $j$ 列的格子。每个 $V_{ij}$ 可以是以下类型之一：

• $0$：表示空单元格。
• $-100000$：表示有障碍物的格子。
• 介于 $-99999$ 与 $-1$ 之间（包含两端）的整数：表示一个陷阱，其强度为 $-V_{ij}$。
• 介于 $1$ 与 $99999$ 之间（包含两端）的整数：表示一个药水，其强度为 $V_{ij}$。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是 Raven 先生到达洞穴出口时能拥有的最大能量点数。如果无法到达出口，则输出 $-1$。

2
4 4 100 1 1 4 4
0 0 0 0
0 0 0 0
0 0 0 -100000
0 0 -100000 0
2 2 100 1 1 2 2
0 0
0 0

Case #1: -1
Case #2: 100

1
8 8 250 7 1 1 7
-100000 -100000 -100000 -100000 -100000 -100000 0 -100000
-100000 0 -100000 0 -400 0 0 -100000
-100000 100 -300 0 -100000 -300 -100000 -100000
-100000 0 -100000 500 -100000 250 0 -100000
-100000 -200 -100000 -100000 -100000 -100000 -100 -100000
-100000 0 -100000 0 0 50 50 -100000
0 0 -100 0 -100000 50 -100000 -100000
-100000 -100000 -100000 -100000 -100000 -100000 -100000 -100000

Case #1: 250

提示

在样例 #1 中，Raven 先生无法到达出口。

在样例 #2 中，没有陷阱也没有药水，这意味着 Raven 先生可以到达出口，并且无论他选择哪条路径，他的能量都将保持不变。

限制条件

$1 \le T \le 100$。

$1 \le N \le 100$。

$1 \le M \le 100$。

$0 \le E \le 100000$。

$1 \le S_R \le N$。

$1 \le S_C \le M$。

$1 \le T_R \le N$。

$1 \le T_C \le M$。

$(S_R, S_C) \ne (T_R, T_C)$。

对于所有 $i, j$，$-100000 \le V_{ij} < 100000$。

最多有 $15$ 个格子满足 $-100000 < V_{ij} < 0$。（最多有 $15$ 个陷阱。）

$V_{S_R S_C} = 0$。（Raven 先生的起始位置是空单元格。）

$V_{T_R T_C} = 0$。（出口所在的格子是空单元格。）

小数据集（测试集 1 – 可见）

没有格子满足 $V_{ij} > 0$。（洞穴中没有药水。）

大数据集（测试集 2 – 隐藏）

无额外限制。

翻译由 DeepSeek V4 Pro 完成