SP10439 WALKROBO - Walking Robot

行走机器人 Leonard 是一名学习机器人技术的学生。他的老师 Dr. Cooper 布置了一个任务，让班级设计一个能够与环境互动，并根据特定事件调整行为的机器人。具体的环境、行为变化和事件由学生自行决定，所以 Leonard 设计了一个能够在网格中行走的机器人，并为其配备了一组移动指令。在网格中特定的位置，机器人可以下载并学习新的移动指令。机器人的目标是用尽量少的步数从网格的起点移动到终点。 该网格共有 $M$ 行和 $N$ 列方格组成。左下角的方格坐标是 $(0,0)$，右上角的坐标是 $(N-1,M-1)$。一个移动指令表示为一个二元组 $(X,Y)$，其中 $X$ 是在 $x$ 轴上的移动量，$Y$ 是在 $y$ 轴上的移动量。每个移动指令都记作一步。机器人不能进行导致其超出网格范围的移动。 在这片网格中，机器人最多可以学习 $K$ 种可能的移动指令。机器人初始时已经知道其中的 $T$ 种移动指令。如果机器人处于下载点，它可以选择花费一步去学习该位置上提供的移动指令。在移动过程中，机器人不能学习新的指令。机器人从坐标 $(0,0)$ 开始，并最终需要移动到坐标 $(N-1,M-1)$。

第一行输入四个整数 $M, N (2 \le M, N \le 15), K (1 \le K \le 12)$ 和 $T (0 \le T \le K)$。接下来的 $K$ 行，每行包含两个整数 $(X, Y) (-10 \le X, Y \le 10)$，分别表示第 $K$ 种移动指令。移动指令从 1 到 $K$ 编号。一行之后有 $T$ 个用空格隔开的整数，表示机器人初始掌握的移动指令编号。接下来是网格的描述：共有 $M$ 行，每行有 $N$ 个整数。0 表示空的方格，正数表示该方格为一个下载点，其值为该点上可下载的移动指令编号。网格中的数值必定在 0 和 $K$ 之间（包括 0 和 $K$）。数据集的最后一组以四个 0 结尾，这组不进行处理。

对于每个测试用例，输出一行，格式为 `Case #X: S`，其中 $X$ 是测试用例的编号（从 1 开始），$S$ 是到达目标所需的最小步数。如果机器人无法到达目标位置，则输出 `-1`。 **本翻译由 AI 自动生成**