|The British Informatics
the computing competition for schools and colleges.
We are proud to present BIO'98.
The 1998 British Informatics Olympiad exam
|A pair of pigs are loose
somewhere in a large wooded area and an experienced
farmer has been sent in to catch them. Your task in this
question is to model their behaviour.
The chase takes place on a 10 by 10 grid, the bottom left square being (1,1). Squares can be empty or contain a tree, the pigs (who always travel together) or the farmer. Only the pigs and the farmer can ever share a square. Each square is represented as follows:
|The pigs wander around the
grid in a set way. They move one square in the direction
they are facing, unless there is a tree or the edge of
the board in the way. If their move was blocked they just
turn 90 degrees clockwise. The farmer, wise in the ways
of pigs, moves in exactly the same way.
The farmer and the pigs can be considered to move simultaneously. If the farmer and the pigs pass each other during a move, they are not considered to have met. Furthermore, due to the difficulty in catching pigs, the farmer and pigs continue to move after they have met.
|Write a interactive program
to model the behaviour of the pigs and farmer. Your
program should first read in a line containing two
numbers, the x co-ordinate then the y co-ordinate of the
pigs. A second line should then be input, consisting of
the co-ordinates for the farmer. Note that both the
farmer and the pigs start by facing up the grid. You
should then output the grid.
Until your program terminates you should repeatedly wait for input, and then:
|Suppose the pigs start at (1,1), and they are trying to reach (10,10). What is the minimum number of trees that need to be placed on the grid to prevent the pigs reaching (10,10)? What is the maximum number that can be placed on the grid so that they can still reach (10,10)?|
|Suppose you are able to place the farmer and the pigs on an empty grid, and you can choose the direction they are both facing (up, down, left or right). For a given starting position either they never meet, or they first meet after x moves. What is the maximum value that x can take?|
|For a given grid, with trees and starting positions (with directions) for the farmer and pigs, will we always be able to determine whether or not the farmer and pigs will meet? Consider both the case where they will eventually meet, and when they will not.|