Unfortunately, the investor is not the owner of all the land between these places. Therefore, some properties have to be bought first.
The land is divided into a regular “grid” of hexagonal parcels, each of them forms an independent unit and has the same value. Some of the parcels belong to the investor. These parcels form four connected areas, each containing one building to be connected with the others. Your task is to find the minimal number of parcels that must be acquired to connect the four given areas.
The whole land also has a hexagonal shape with six sides, each consisting of exactly H parcels.
The above picture shows a land with H = 4, parcels with letters represent the four areas to be connected. In this case, it is necessary to buy four additional parcels. One of the possible solutions is marked by crosses.
The character representing a parcel will be either a dot (“ .”) for the land that is not owned by the investor, or one of the uppercase letters “A”, “B”, “C”, or “D”. The areas of parcels occupied by the same letter will always be connected. It means that between any two parcels in the same area, there exists a path leading only through that area.
Beside the characters representing parcels, the lines may contain any number of spaces at any positions to improve “human readability” of the input. There is always at least one space between two letters (or the dots). After the land description, there will be one empty line and then the next scenario begins. The last scenario is followed by a line containing zero.
Areas are considered connected, if it is possible to find a path between them that leads only through parcels that have been bought.
4 B . . C . . . . C . A . . C . . A A . . . . . A . . . . . . . D D . . . . 0
You have to buy 4 parcels.