| History of OI -> I OI 1993/1994 -> Problems |  |
|
I Olympiad in Informatics 1993/1994
|
|
Task: PIO
|
Author: Andrzej Walat
|
| I stage contest |
We have a square board having 8x8 squares numbered as in the picture below, and 64 white draughtsmen and 64 black draughtsmen.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 |
| 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 |
| 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |
| 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 |
| 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 |
| 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 |
We are given an initial arrangement of draughts on the board, such that every square is occupied by exactly one draught of any colour. Our purpose is to obtain such an arrangement that all draughts on the board have the same colour, and we are going to reach this in as few moves as possible.
In a single move one points a number of any board square - we call the square a centre of changes. Then one exchanges the draughts on all the squares touching a side or a corner of the indicated centre of changes with opposite colour draughts. The draught in the centre is not exchanged. In the next move one points another square as a centre of changes, exchanges adjacent draughts accordingly, and so on.
The input data is a sequence of eight words, written in eight successive lines corresponding to the eight rows of the board. Every word consists of eight letters B (for "white") or C (for "black") describing the draughts' colours in the eight consecutive squares of the respective board row.
The answer in the first line should contain the minimal number of moves required. If the number is zero, that only line ends the answer. Otherwise, starting from the next line there should be given numbers of successive centres of changes, separated by a space or a single end-of-line character.
When there are many ways of getting a one-coloured arrangement in the minimal number of moves, one should present only one of them.
If the data is not correct, i.e. does not meet the above conditions, the word NONSENS ("nonsense") is the answer.
Examples
For the data file:
CCCCCCCC BBBBBBBB CCCCCCCC CCCCCCCC CCCCCCCC CCCCCCCC CCCCCCCC CCCCCCCCthere is an example of correct answer:
26 57 59 62 64 50 55 42 47 33 35 38 40 25 26 28 29 31 32 18 19 22 23 2 3 6 7For the data file:
CCCCCCCC CCCCCCCC CCCCCCCC CCCCCCCC CCCCCCCC CCCCCCCC CCCCCCCC CCCCCCCCthe correct answer is:
0For the data file:
CCCCCCCC CCDDCCCCC CCCCCCCC CCCCCCCC CCCCCCCC CCCCCCCC CCCCCCCC CCCCCCCCthe correct answer is:
NONSENS
Task
Write a program, that successively for every data set from a file PIO.IN generates a correct answer and writes it to a file PIO.OUT.
The source text of the program should be written in a file named PIO.???, where ??? are substituted by a sequence of letters appropriate for the programming language used.
The executable program should be named PIO.EXE.