UVA1170 Jumping Hero

**背景**：一天，一个软件公司决定做一个游戏，以迷宫为主题。主角要从起点走到终点。在迷宫中，有一些单元格包含魔法喷泉，可以用来获得超能力。 通常情况，主角可以向上/下/左/右移动到一个空单元格。每当主角进入一个有魔法喷泉的单元格时，他会获得超能力，主角可以用超能力跳到当前单元格左/右/上/下的第 $N$ 个单元格。超能力持续 $M$ 次跳跃，英雄可以在每次跳跃后改变其跳跃方向。如果跳跃的结束单元格在地图中并且不是墙，那么英雄可以跳过墙。如果英雄带着魔法喷泉效果跳到另一个有魔法喷泉的单元格，他将获得新魔法喷泉的超能力，前一个魔法喷泉的效果将被覆盖。如果英雄跳到他获得当前超能力的单元格，则不会产生任何效果（也就是说，能力不可叠加，英雄不可以获得额外的超能力）。 当当前的超能力结束时，英雄将继续其正常的移动。如果在某个喷泉中获得超能力后，英雄不能移动到任何单元格中，他就会失去超能力，回到之前的房间中。为了到达结束位置，英雄必须移动到结束单元格或在结束单元格中完成一次跳跃。 给定迷宫地图，计算从起始位置到结束位置的最小跳跃/移动次数。

输入包含多组数据。 输入的第一行是一个整数，表示数据集个数。 每个数据集的第一行包含两个正整数，$L$ 和 $C$，用一个空格隔开，其中 $L$ 表示迷宫的行数，$C$ 表示迷宫的列数。$L$ 和 $C$ 都小于 $300$。 下面 $L$ 行每行包含 $C$ 个整数，表示迷宫的所有单元格（每两个单元格间用一个空格分隔）。每个表示单元格的整数 $i$ 必须解释如下：$i = 0$ 表示一堵墙；$i = 1$ 表示一个空单元格（英雄可以移动到的地方）；$i = 10m + n$ 表示一个空的单元格，其中有一个魔法喷泉，可以让英雄跳 $m$ 次，跳到第上/下/左/右的第 $n$ 个单元格。$m$ 的取值范围是 $1 \sim 5$，$n$ 的取值范围是 $2 \sim 6$。 每一组输入的最后两行表示起始位置和结束位置的坐标（坐标由两个整数组成，分别表示从 $0$ 开始的行和列）。

输出到达结束位置的最小跳跃/移动次数，若无法到达结束位置，则输出 `impossible`（单独一行）。在每行数据间空行。

地图中魔法喷泉的最大数量是 $5000$ 个。