ROSECODE 016
Swamp Kangaroo
Kangaroos are fascinating creatures. For one, the idea of carrying around their offspring in a pouch is very cute, and it
reminds us of our own ways of transporting babies. For another, they can jump really far. That can be quite useful, in
particular if you are a kangaroo stuck in a swamp with only small islands of land, and crocodiles swimming around. In
that case, you would rather not land in the water. Besides mere jumping strength, it is also useful to have some computational
power to compute how exactly to use that jumping strength to get where you need to go.
Here is how we model Kangaroo movement. Kangaroos can only move North-South or East-West; no other directions (such as diagonals). Kangaroos can jump any integer distance between 1 and 5 in one hop, which takes them one unit of time. However, after a longer jump, they have to rest before being able to jump again. Specifically, after jumping distance d, the Kangaroo has to rest (d - 1)^2 time units before being able to jump again. Also, if the next jump is in a different direction from the previous one, the Kangaroo takes an extra one time unit between the jumps to turn around.
The swamp will be described by a two-dimensional grid. Each entry is either water, denoted by a dot (.), or land, denoted by X. Two locations will be marked with special symbols. K denotes the initial position of the Kangaroo, and G is the goal the Kangaroo wants to reach (both of these are of course land). You are to find the shortest time in which the Kangaroo could get to the goal (if at all). It does not matter if the kangaroo is tired when it arrives at its destination; it doesn not have to rest.
What is the answer for the following input?
.......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..
.......XX................XXX..
Source:USC Contest Fall 2008
Here is how we model Kangaroo movement. Kangaroos can only move North-South or East-West; no other directions (such as diagonals). Kangaroos can jump any integer distance between 1 and 5 in one hop, which takes them one unit of time. However, after a longer jump, they have to rest before being able to jump again. Specifically, after jumping distance d, the Kangaroo has to rest (d - 1)^2 time units before being able to jump again. Also, if the next jump is in a different direction from the previous one, the Kangaroo takes an extra one time unit between the jumps to turn around.
The swamp will be described by a two-dimensional grid. Each entry is either water, denoted by a dot (.), or land, denoted by X. Two locations will be marked with special symbols. K denotes the initial position of the Kangaroo, and G is the goal the Kangaroo wants to reach (both of these are of course land). You are to find the shortest time in which the Kangaroo could get to the goal (if at all). It does not matter if the kangaroo is tired when it arrives at its destination; it doesn not have to rest.
What is the answer for the following input?
.......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..
.......XX................XXX..
Source:USC Contest Fall 2008