Centipede is a classic computer game where the main feature is a centipede
moving horizontally across the screen. When it bumps into an obstacle,
it changes direction and moves down one row.
The centipede consist of 10 segments. The first segment is the head, while
the remaining segments make up the tail. The second segment
will be located where the head was one time unit ago, the third segment
where it was two time units ago, etc. Several segments might share the same location at
the same time, see example 0.
When the centipede starts (at time 0), or has just completed a cycle (see below), it will
occupy the leftmost 10 free squares in the first row. The head
is in the rightmost of these squares, and the horizontal direction is right.
Every time unit, the centipede moves one square in its current horizontal direction if possible.
If this is not possible due to an obstacle, it moves one square down and changes direction (from
right to left or from left to right). If this isn't possible either, it only changes direction (and doesn't move horizontally at all, see
example 0).
When the centipede bumps into an obstacle on the last row, it will move down
out of the screen. In the same time unit as the last segment
leaves the screen, the whole centipede will reappear on the first row.
We say that the centipede has completed a cycle, and that the time unit when
this happens for the first time is the cycle length. You may assume that
given enough time, the centipede will always be able to complete a cycle. That is,
it will never get stuck.
Given a screen layout containing where the obstacles are, you are to compute the
location of the centipede after a given number of
time units. This number may be very big, see example 4.
Obstacles are marked with a '#' on the layout. The first and last column in each row will
always be an obstacle, and the first row will contain no other obstacle.
Below to the left is an example of a screen layout (quotes for clarity only),
while below to the right is the same layout with a centipede trace, marking all the squares
that some part of the centipede will visit.
"# #" "xxxxxxxxxxxxxxxxx"
"# # # #" " # #xxxxxxxx"
"# # # # #" " # #xxx# "
"# # #" " xx# "
"# ## # #" " ##xxxxxx # "
"# # ## #" " # xxx## "
"# # #" " #xxx "
"# #" " xxxxxxxxxxxx"
Create a class Centipede containing the method simulate which takes
a String[] screenLayout containing the layout in the format
described above, and an int timeUnits, the number
of time units to simulate. The method should return a String[]
containing the same layout, except that the squares which are occupied
by a centipede segment after timeUnits time units should be changed
to a lowercase 'x'.
|