[BIO Logo] The British Informatics Olympiad is
the computing competition for schools and colleges.
We are proud to present BIO 2000.
-----

The 2000 British Informatics Olympiad - Round One

Question 2
Ants		 Two ants are crawling over a virtual landscape, changing the scenery as they move. Your task in this question is to model their behaviour.

The landscape is an 11 by 11 grid. The bottom left square is at (1,1) and the x-axis runs along the bottom of the grid. Each square is coloured either black or white. A square can contain either, both or neither of the ants.

Each ant wanders around the grid in a set way. An ant moves one square forward in the direction it is facing. If the square it lands on is black it rotates 90° left, if it is white it rotates 90° right. The colour of the square it is on is then changed. An ant that moves off the edge of the board is removed from the simulation. For example:

[Graphic of example]

  In each move of the simulation, the ants move in turn as follows. First, ant 1 moves as described above. Once its final step is complete, i.e. once it has changed the colour of the square it landed on, ant 2 moves.
2 (a)
[30 marks]		 Write an interactive program to model the behaviour of the ants. Your program should first read in two lines, describing the starting position of ants 1 and 2 respectively. Each line will contain two numbers, the x co-ordinate then the y co-ordinate of the ant, followed by a letter indicating the direction the ant is facing. The letter, 'T', 'B', 'L' or 'R', indicates the top, bottom, left or right of the grid.

The landscape starts off with every square white.

Until your program terminates you should repeatedly wait for input and then:

  1. If you receive an integer 'n' you should calculate 'n' moves from the current position. You should then display the landscape, using '.' for white squares and '*' for black squares. You should then print out the co-ordinates and direction of each ant, or Removed if the ant is not longer on the board.

  2. If you receive the number -1 you should terminate.

  3. Ignore any other input.

 Sample run
5 5 T
3 9 B
 
6
...........
...........
.**........
.*.*.......
...........
...*.*.....
....**.....
...........
...........
...........
...........
4 6 T
4 8 B
 
1
...........
...........
.**........
.*.*.......
...........
...*.*.....
....**.....
...........
...........
...........
...........
4 7 R
4 7 R
 
59
...**......
..****.....
.*.**.*....
*...***....
.*...*.....
*.*..*.....
.*...*.....
.*...*.....
..*..*.....
...**......
...........
6 4 B
Removed

-1
2 (b)
[5 marks]		 [Example] What did the landscape shown on the left look like 6 moves earlier?

[Draw the landscape, and write the co-ordinates and directions for the two ants using the same notation as for question 2(a).]
2 (c)
[5 marks]		 At the start of the simulation Ant 1 is facing left. Much later in the simulation there is an ant on the same square facing top. Can it be the same ant? Justify your answer.
The British Informatics Olympiad