<PREV Problem:
NEXT>
Solved by 189 users: ...
UserDateAttemptTimeCMSC
Philip_PV31 jul 2009FPC3000.11386 
Philip_PV31 jul 2009FPC2900.10392 
tomek19 feb 2006C++200.02401 
deCart24 nov 2006FPC400.02418 
glueray15 nov 2006C++1700.01420 
DAV25 mar 2009C++1800.06421 
MasterYoda01 apr 2009C++1300.02428 
sazuki04 apr 2008C800.01434 
Ra16bit15 mar 2008FPC100.01437 
DAV24 mar 2009C++1700.06444 
MasterYoda29 mar 2009C++700.02448 
glueray15 nov 2006C++1500.01455 
MasterYoda29 mar 2009C++600.02456 
svirg11 oct 2007C++1000.04466 
DAV23 mar 2009C++1600.05482 
vi00210 oct 2007C++1500.04483 
Languages
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 DevGroup
The page was generated in 180ms

SW soft NIX
ID = 3.237.200.21