Solved by 189 users: ...
UserDateAttemptTimeCMSC
Philip_PV`31 jul 2009`FPC3000.11386
Philip_PV`31 jul 2009`FPC2900.10392
tomek`19 feb 2006`C++200.02401
deCart`24 nov 2006`FPC400.02418
glueray`15 nov 2006`C++1700.01420
DAV`25 mar 2009`C++1800.06421
MasterYoda`01 apr 2009`C++1300.02428
sazuki`04 apr 2008`C800.01434
Ra16bit`15 mar 2008`FPC100.01437
DAV`24 mar 2009`C++1700.06444
MasterYoda`29 mar 2009`C++700.02448
glueray`15 nov 2006`C++1500.01455
MasterYoda`29 mar 2009`C++600.02456
svirg`11 oct 2007`C++1000.04466
DAV`23 mar 2009`C++1600.05482
vi002`10 oct 2007`C++1500.04483
 FPC 88 C++ 81 Kylix 13 Java 4 C 4 Python 1
` >  >  >  >  >  >  >  >  >  > `

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

 Input#1```5 6 BBBBBZ BCCCBZ BCAbbZ BDDDbZ 33333Z ``` Output#1```4 ```

Author:
Student olympiad in Khmelnitski, March 2003
24 april 2003

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

 © acm.mipt DevGroupThe page was generated in 200ms