<PREV Problem:
Solved by 188 users: ...

Storm in a Rectangle

Time limit = 1

Saddamia State is a rectangle composed of M x N unit squares. Saddamia is divided into K provinces (2 ≤ K ≤ 100). Each province is a connected set of units, it means than its possible to go from each one point of province to another one. Going from one unit to another is allowed only if they have common edge (common vertex is not enough). There is no point in Saddamia which is contiguous with more then 3 provinces (it means that 4 unit squeares with common vertex cant be of 4 different provinces).

Each province has his own symbol. The Saddamia Capital is situated in province A (capital Latin character A). Province is called Frontier if it has one or more boundary units. Province A is not a frontier. The King of Bushlandia made up his mind to win the Saddamia.

In compliance with a confidential agreement with U.N.O. he should force the King of Saddamia to yield himself prisoner. Accordantly with a plan of the King of Bushlandia the King of Saddamia would yield himself prisoner, if the province with the capital will be rounded up.

It's necessary to occupy all provinces around to make the province rounded up.

To occupy province it's necessary to satisfy one of two conditions: 1) the province is a frontier or 2) has common edge with a province already occupied.

To minimize the own battle casualties the King of Bushlandia have a plan to set up a blockade of the province with the capital throughout the occupation of the minimum provinces before. The problem is to determine the minimum quantity of provinces to be occupied (province with the capital could not be occupied).

Input The first line consists of two numbers: M and N (3 ≤ M, N ≤ 200). The next M lines consist of N characters per line and define the map of Saddamia. The symbol situated in (i+1)-th row of the text in j-th position is represent the symbol of the province of the unit (i, j). All characters are ASCII-coded (code > 32). The input is guaranteed to be correct.

Output One integer number = quantity of the provinces to be occupied. If it is impossible to set up a blockade, then you should output -1.

5 6

Student olympiad in Khmelnitski, March 2003
24 april 2003

<PREV | Problem set | Search related messages | NEXT>

© acm.mipt DevGroup
The page was generated in 190ms

SW soft NIX
ID =