P16658 [GKS 2018 #G] Cave Escape

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$。

在样例 #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 完成