4th Balkan Olympiad in Informatics
Nicosia, Cyprus, 19-25 October 1997
Day 1 - Problem 3 (Heads and tails)
A NxN matrix (where N<=10) of coins is given, some heads up and some tails up. A player
must flip coins so as to achieve an all tails configuration. However, when a player flips
a particular coin, each rectilinearly adjacent neighbors (i.e. its left, right, top and
bottom neighbors, if they exist), also flip over.
The problem is, given an initial configuration, to achieve an all tails matrix by flipping
the minimum number of coins. Note that by flip we mean "point to a coin, and change
it and its neighbors".
 |
Input:
INPUT DATA (file INPUT.TXT)
The first line contains the integer N. Each of the next N lines contains N characters, H
or T standing for the heads/tails respectively.
|
|
Output:
OUTPUT DATA (file OUTPUT.TXT)
The first line should contain the minimum number of flips. The next N lines comprise a
matrix of N integers per line. hese integers have an 1 or a 0 value. The value 1 means
that the corresponding coin has been flipped at least once. The alue 0 means that the
corresponding coin has not been flipped at all.
|
|
Examples:
- Input
3
H T T
H T T
T T T
- Output
5
1 0 0
0 1 0
1 1 1
|
|
Remark You may assume
that there is always a solution to the problem.
|
Time-limit for each test: 20 seconds.
Maximal score: 40 points