Program | COLLIDE.C, COLLIDE.CPP, COLLIDE.PAS |
A small boy named Tommy has some toy centipedes that are a series of 1 centimeter
segments. Tommy assembles his centipedes to any length he likes and places them
on a 30x30 centimeter board that allows the centipedes to travel in 1 centimeter
wide tracks that criss-cross the board. The centipedes travel only parallel
to either the x or y axis on the board. Centipede segments of the same centipede
advance at the same time and centipedes advance in cyclic numerical order (all
of centipede 0 first, then 1, etc.). When more than one segment of two or more
centipedes occupy the same x,y coordinate, there is a centipede collision. Anytime
a collision occurs, all segments occupying the collistion site stop and continue
to occupy the collision site. All remaining segments on a centipede detach from
the segment involved in the collision and continue their march until another
collision occurs or an existing collision site is encountered or until the segments
fall off the edge of the board. Anytime a segment enters a collision site, it
becomes part of the collision.
Since Tommy left home without his centipede set, his mother has hired you to
write a simulation program for his entertainment. Your program will simulate
his board with a text printout of his grids. For example, Tommy may simulate
5 centipedes on his board that start out as shown on the grid on the left and
finish as shown on the grid on the right (note the example grid is only 10x10
whereas Tommy's is 30x30.)
9 . . . . . . . . . . 9 . . . . . . . . . . 8 . . . . . . . . . . 8 . . . . . . . . . . 7 1 1 1 1 1 . . . . . 7 . . . . . X . . . X 6 . 0 . . . . . . . . 6 . . . . . . . . . . 5 . 0 . . . . . . . 3 5 . . . . . . . . . . 4 . 0 . . . 2 . . . 3 4 . . . . . . . . . . 3 . 0 . . . 2 . . . 3 3 . . . . . . . . . . 2 . . . . . 2 . . . 3 2 . . . . . . . . . . 1 . . . . . 2 . . . 3 1 . . . . . . . . . . 0 . . . . . 2 4 4 4 3 0 . X . . . . . . . . Y Y / X 0 1 2 3 4 5 6 7 8 9 / X 0 1 2 3 4 5 6 7 8 9
Your program will simulate up to 10 centipedes that travel on a 30x30 board. Tommy has 100 segments that he may use in his simulation. Of course, no centipede can be longer than 30 segments.
For each input simulation set, you should print the number of cells that contains
2 or more centipede segments involved in a collision, as well as coordinates
of these cells. Follow the Sample Output for the exact format of the expected
output.
Sample Input
10
R 9 11 23
U 8 11 17
U 5 15 15
U 5 15 8
D 9 23 13
U 6 23 6
R 9 8 9
L 13 17 0
U 12 13 11
L 5 20 9
Sample Output
5 (23, 11) (23, 15) (9, 13) (9, 15) (9, 23)