ROSECODE 016
沼泽袋鼠
Swamp Kangaroo
袋鼠是一种迷人的生物。其一，将后代装在育儿袋里随身携带的想法非常可爱，而且
让我们想起我们自己运送婴儿的方式。另一方面，他们可以跳得很远。这可能非常有用，在
特别是如果你是一只困在沼泽里的袋鼠，沼泽里只有小岛，鳄鱼在周围游动。在
这种情况下，你宁愿不落入水中。除了单纯的跳跃力量之外，具备一些计算能力也很有用
计算如何准确地使用跳跃力量到达您需要去的地方的能力。
这是我们模拟袋鼠运动的方式。袋鼠只能从北向南或从东向西移动；没有其他方向 （如对角线）。袋鼠可以在一跳中跳跃 1 和 5 之间的任意整数距离，这需要它们的一个单位 时间。然而，在跳了更长的距离后，他们必须休息才能再次跳跃。具体来说，跳跃后的距离 d，袋鼠必须休息 (d - 1)^2 时间单位才能再次跳跃。另外，如果下一次跳转是在不同的 与上一次的方向相比，袋鼠在跳跃之间需要额外的一个时间单位才能转身。
沼泽将通过二维网格来描述。每个条目要么是水，用点 (.) 表示，要么是土地，用点 (.) 表示 通过 X。两个位置将标有特殊符号。 K 表示袋鼠的初始位置，并且 G 是 袋鼠想要达到的目标（当然都是陆地）。你要找出最短的时间 袋鼠可以达到目标（如果有的话）。袋鼠到达目的地时是否累了并不重要；它 不必休息。
以下输入的答案是什么？
......XXX......XX......X.X.XX。
XK..XXXXXXXX..XX............
X......XXXXX..XX.X.X.X....X。
......XXX......XX............
......XX......XX。
………………XX。
...XX..XX................XX。
..XXXX..................X..
..XXXX........................
...XX....XX..X....XXX..
........XX..XX.X..X..X.XGX..
…………………………………………………………………………………………………………………………………………
资料来源：南加州大学秋季竞赛 2008
这是我们模拟袋鼠运动的方式。袋鼠只能从北向南或从东向西移动；没有其他方向 （如对角线）。袋鼠可以在一跳中跳跃 1 和 5 之间的任意整数距离，这需要它们的一个单位 时间。然而，在跳了更长的距离后，他们必须休息才能再次跳跃。具体来说，跳跃后的距离 d，袋鼠必须休息 (d - 1)^2 时间单位才能再次跳跃。另外，如果下一次跳转是在不同的 与上一次的方向相比，袋鼠在跳跃之间需要额外的一个时间单位才能转身。
沼泽将通过二维网格来描述。每个条目要么是水，用点 (.) 表示，要么是土地，用点 (.) 表示 通过 X。两个位置将标有特殊符号。 K 表示袋鼠的初始位置，并且 G 是 袋鼠想要达到的目标（当然都是陆地）。你要找出最短的时间 袋鼠可以达到目标（如果有的话）。袋鼠到达目的地时是否累了并不重要；它 不必休息。
以下输入的答案是什么？
......XXX......XX......X.X.XX。
XK..XXXXXXXX..XX............
X......XXXXX..XX.X.X.X....X。
......XXX......XX............
......XX......XX。
………………XX。
...XX..XX................XX。
..XXXX..................X..
..XXXX........................
...XX....XX..X....XXX..
........XX..XX.X..X..X.XGX..
…………………………………………………………………………………………………………………………………………
资料来源：南加州大学秋季竞赛 2008