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".

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.

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.

  • Input
    H T T
    H T T
    T T T
  • Output
    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