题目描述

你是龙之国的王子，你的王国正面临能源耗尽的危险。你必须寻找能量来拯救你的王国和人民。一个古老的传说提到，能量来自一个被称为“龙之迷宫”的地方。龙之迷宫会毫无征兆地随机出现，又会毫无警告地突然消失。你知道龙之迷宫现在的位置，所以你必须趁它消失前获取一些能量，这一点至关重要。

龙之迷宫是一个矩形迷宫，一个 $\mathbf{N} \times \mathbf{M}$ 的格子网格。迷宫的左上角格子是 $(0,0)$，右下角是 $(\mathbf{N}-1, \mathbf{M}-1)$。组成迷宫的每个格子要么是一个一旦进入就永远无法逃脱的危险之地，要么是一个包含一定量能量的安全之地。安全格子中的能量在你进入该格子时会自动收集，并且只能被收集一次。从一个格子出发，你可以向上/下/左/右走到相邻的格子，每移动一次算作一步。

现在你知道入口格子和出口格子的位置，它们是不同的，并且都是安全格子。为了在龙之迷宫消失之前走出去，你必须从入口格子走到出口格子，并尽可能走最少的步数。如果有多种路径可以选择，你必须选择那条能收集到尽可能多能量的路径，以便拯救你的王国。

输入格式

输入的第一行给出测试用例的个数 $T$。接下来是 $T$ 个测试用例。

每个测试用例的第一行包含两个整数 $\mathbf{N}$ 和 $\mathbf{M}$，描述如上所述的龙之迷宫的尺寸。 每个测试用例的第二行包含四个整数 $\text{en}_{\text{x}}, \text{en}_{\text{y}}, \text{ex}_{\text{x}}, \text{ex}_{\text{y}}$，描述入口格子 $(\text{en}_{\text{x}}, \text{en}_{\text{y}})$ 和出口格子 $(\text{ex}_{\text{x}}, \text{ex}_{\text{y}})$ 的位置。 接下来是 $\mathbf{N}$ 行，每行有 $\mathbf{M}$ 个由空格分隔的数字，从上到下描述龙之迷宫 $\mathbf{N} \times \mathbf{M}$ 的格子。每个格子的数字要么是 $-1$，表示该格子是危险的，要么是一个正整数，表示该格子是一个包含一定量能量的安全格子。

输出格式

对于每个测试用例，输出一行形如 Case #x: y 的内容，其中 $x$ 是测试用例编号（从 $1$ 开始）。如果你能够从入口走到出口，则 $y$ 应该是在走最少步数的前提下，你能收集到的最大总能量。如果你无法从入口走到出口，则 $y$ 应该是字符串 Mission Impossible.。请注意，评测系统要求精确匹配，因此任何其他输出，例如 mission impossible. 或 Mission Impossible（缺少结尾的句号），都将被判定为不正确。

2
2 3
0 2 1 0
2 -1 5
3 -1 6
4 4
0 2 3 2
-1 1 1 2
1 1 1 1
2 -1 -1 1
1 1 1 1

Case #1: Mission Impossible.
Case #2: 7

提示

限制

每个格子中所含的能量值不会超过 $10,000$。

$1 \le T \le 30$。

$0 \le \text{en}_{\text{x}}, \text{ex}_{\text{x}} < N$。

$0 \le \text{en}_{\text{y}}, \text{ex}_{\text{y}} < M$。

测试集 1 - 可见

$1 \le \mathbf{N}, \mathbf{M} \le 10$。

测试集 2 - 隐藏

$1 \le \mathbf{N}, \mathbf{M} \le 100$。

翻译由 DeepSeek V4 Pro 完成