Hexagonal Parcels
Time limit1sMemory limit128 MB
On a hexagonal grid with four labeled connected regions, find the minimum number of free cells to buy so all four regions become one connected component (Steiner-tree style optimization on a hex graph).
- Level
Hard8 of 10
- Topics
- Graph, BFS, Dynamic programming
- Solved
- No attempts yet
Problem
A civil engineer must connect several buildings with an infrastructure network. The investor does not own all of the land between the buildings, so some parcels have to be bought first.
The land is divided into a regular grid of hexagonal parcels. Every parcel is an independent unit and all parcels have the same value. Some parcels already belong to the investor; they form four connected areas, and each area contains one building that has to be connected with the others. Your task is to find the minimum number of additional parcels that must be acquired so that the four areas become connected.
The whole land also has the shape of a hexagon whose six sides each consist of exactly H parcels. Every parcel is either free — a dot (.) — or owned by the investor and marked with one of the uppercase letters A, B, C, or D naming its area. Parcels with the same letter always form one connected area. For example, for H = 4 and the areas placed as in the first sample, four extra parcels are enough to connect all four areas.
Input
The input contains several scenarios. Each scenario begins with a line holding one integer H (2 ≤ H ≤ 20), the size of the land. It is followed by 2·H − 1 lines that describe the rows of the hexagon: the first line lists H parcels, the second H + 1, and so on up to the middle line with 2·H − 1 parcels, after which the length decreases again down to H in the last line.
Each parcel is written with a single non-space character: a dot (.) for free land, or one of A, B, C, D. The lines may contain any number of extra spaces at any position for readability, but there is always at least one space between two parcel characters. After every land description there is one empty line. The last scenario is followed by a line containing a single 0, which must not be processed.
Output
For each scenario print one line in the exact form:
You have to buy P parcels.
where P is the minimum number of parcels that have to be bought so that all four areas become connected. Two areas are connected when there is a path between them that runs only through parcels which are owned by the investor or have been bought; the free parcels that are not bought act as barriers.