Blockade (solution through graphs)

All-Russian Team Olympiad in Programming, 2001

The task

The state of Flatland is a rectangle of size M x N, consisting of unit squares. Flatland is divided into K provinces (2 <= K <= 100). Each province is a connected set of squares, that is, from each point of the province you can reach any other point, while it is allowed to move from square to square only if they have a common side (there is not enough common vertex). There is no point in Flatland that borders with more than three provinces (that is, four squares with a common vertex cannot belong to four different provinces). Each province has its own symbol. The capital of Flatland is located in the province, which has the symbol A (capital Latin letter A). A province is called border if it contains boundary squares. The province in which the capital of Flatland is located is not border.

The king of Rektilania, next to the kingdom of Flatland, decided to conquer Flatland. For this, he wants to seize the capital of Flatland. However, he knows that the strength of his army is not enough to do it right away. Therefore, he first wants to surround the central province, weaken the enemy's forces by a long blockade, and then seize the capital.

To surround the province, you want to capture all the provinces with which it borders. Two provinces border if there are two squares with a common side, one of which belongs to the first one, and the other one to the second. To seize a province, it is necessary that one of two conditions be fulfilled: either it is borderline, or it borders on any province that has already been seized.

In order to preserve the strength of his army, the king of Rektilania wants to blockade the central province, capturing as few provinces as possible. Help him figure out how many provinces you need to capture. It is impossible to seize the central province itself, since for this the forces of the Rektilania army are not enough.

Input

The first line contains M and N (3 <= M, N <= 200). The next M lines contain N characters each and define a map of Flatland. The symbol in the (i + 1) -th line of the input file at the j-th place is a symbol of the province that owns the box (i, j). All characters have an ASCII code greater than 32.

Conclusion

Output in the output file a single number - the number of provinces that you want to capture. If it is impossible to establish a blockade, output “-1”.

  Input Example Output Example
 5 6 4 
 BBBBBZ 
 BCCCBZ 
 BCAbbZ 
 BDDDbZ 
 33333Z 

  7 6 5
 Zzzzzzz
 NDDDDL
 NRCCDL
 NBACDL
 NNOKKL
 NNGGGG
 PPPPPP

Decision

Transition to graphs is carried out as follows: vertex - area (indicated by a symbol with a possible code from 32 to 255). The edge displays the adjacency of the two regions. When entering the initial data, two adjacent lines are analyzed: adjacent (horizontal) characters in the second line and adjacent (vertically) characters of the first and second lines. According to this data, the edges of the graph are replenished.

The areas adjacent to the area A to be blocked are immediately included in the list of areas to be captured. We denote their number by the variable A. Then, using the Dijkstra algorithm, we find the shortest distances from the outer region to all the specified regions.

If any of the areas adjacent to area A is unreachable, then output the answer "-1" and stop the program.

Cycle by the number of areas adjacent to A:
- all new vertices included in the optimal path are added to the list of all the different vertices needed to capture area A;
- reset the weights of all edges associated with the vertices that are included in the optimal path;
- Dijkstra's algorithm finds new shortest distances to all vertices.

After this cycle is completed, we display the number of vertices in the created list.

Formal description

  Blockade ()
 1. Read the country map from the file.
 2. Create a graph on the basis of the map (carry out clauses 2.1-2.3):
 2.1.  Initialize adjacency matrix with zeros.
 2.2.  For each map square, check 4 adjacent squares and if
 the adjacent square is different from the current one, then connect the data
 province edge.
 2.3.  If the square lies on the border of the map, then connect this province
 with the outer country.
 3. Apply the Dijkstra algorithm to find the shortest path from the external
 countries in the capital (perform paragraphs.3.1.-3.3):
 3.1.  Initialize the distance to the vertices to infinity,
 all tags about finding the shortest path to zeros.
 3.2.  Set the distance to the starting vertex to be 0.
 3.3.  Until the shortest paths are found for all vertices, repeat
 pp  3.3.1-3.3.3:
 3.3.1.  Find the top, the shortest path for which is not found,
 with a minimum distance.
 3.3.2.  Assume that the shortest path for this vertex is found.
 3.3.3.  Update the distance to the incident to the current vertices.
 4. If the capital exists and all the neighboring peaks are reachable,
 then execute pp.4.1.-4.4 the number of times equal to the number of vertices
 incident capital, otherwise to display a message about the impossibility of the blockade.
 4.1.  Remove the edge between the capital and the predecessor in the shortest way.
 4.2.  Set the values ​​for the edges used in the shortest route
 weight equal to 0.
 4.3.  Add vertices used in the shortest route to the set
 trapped vertices.
 4.4.  Apply Dijkstra's algorithm to find the shortest path out of
 foreign countries to the capital (perform paragraphs.3.1.-3.3).

Consider the solution to the problem for the second input example . After initializing and transforming the incidence relation on the map into a link on the graph, we obtain a graph of 13 vertices (13 provinces) connected by edges as follows:

  Area Adjacent areas

 Z NDL External
 N ZDRBOGP External
 D ZNLRCK
 L DKG Exterior
 R NDCB
 C DKAR
 B NRA
 A CBO
 O nkag
 K CDLGO 
 G OKLNP Exterior
 P NG Exterior
 External ZNLGP

We apply the Dijkstra algorithm to the resulting graph three times (the degree of apex-capital), each time removing the edge to the top-capital, and the used paths are zeroed.

Below are the states of the graph on each of the three iterations. The capital and the outer country are indicated by a blue frame. The vertices that you need to capture - red frame. Used paths for the current route are indicated in red. Above the previously used edges is the digit 0.

We are looking for captured vertices and their number (marked with a red frame on the graph). For this example, for the blockade of the capital, it is necessary to capture 5 provinces: N, D, B, C, O.