<ПРЕД Задача:
СЛЕД>
Задачу решили 189 пользователей: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Шторм в прямоугольнике

Time limit = 1

Государство Саддамия представляет собой прямоугольник размером MxN, состоящий из единичных квадратиков. Саддамия разделена на K провинций (2 ≤ K ≤ 100). Каждая провинция представляет собой связное множество квадратиков, т.е. из каждой точки провинции можно дойти до любой другой точки, при этом разрешается переходить с квадратика на квадратик, только если они имеют общую сторону (общей вершины недостаточно). В Саддамии нет точки, которая граничила бы более, чем с тремя провинциями (т.е. четыре квадратика, имеющие общую вершину, не могут принадлежать четырем разным провинциям).

Каждая провинция имеет свой символ. Столица Саддамии находится в провинции, обозначаемой символом A (заглавная латинская буква A). Провинция называется пограничной, если она содержит один или более граничных квадратиков (находящихся на границе прямоугольника). Провинция, в которой находится столица Саддамии, не является пограничной.

Король государства Бушландия решил завоевать Саддамию. По секретной договоренности с ООН для этого он должен вынудить короля Саддамии сдаться в плен. По плану короля Бушландии король Саддамии сдастся в плен, если окружить столичную провинцию.

Чтобы окружить провинцию, требуется захватить все провинции, с которыми она граничит. Две провинции граничат, если существует два квадратика, имеющие общую сторону, один из которых принадлежит первой из них, а другой — второй. Чтобы захватить провинцию, надо чтобы выполнялось одно из условий: либо она пограничная, либо граничит с какой-либо уже захваченной провинцией.

Чтобы минимизировать потери своей армии, король Бушландии хочет установить блокаду столичной провинции, захватив как можно меньше провинций. Помогите ему выяснить, сколько провинций требуется захватить (захватывать столичную провинцию нельзя).

Вход Первая строка содержит числа M и N (3 ≤ M, N ≤ 200). Следующие M строк содержат по N символов каждая и задают карту Саддамии. Символ, находящийся в i-ой строке теста на j-м месте, представляет символ провинции, которой принадлежит квадратик (i, j). Все символы имеют ASCII-код больше 32 (пробела). Корректность исходных данных гарантируется.

Выход Одно число равное количеству провинций, которые требуется захватить. Если установить блокаду невозможно, выведите -1.

Вход#1
5 6
BBBBBZ
BCCCBZ
BCAbbZ
BDDDbZ
33333Z
Выход#1
4

Автор:
Полуфинал Украины среди ВУЗов, март 2003, г. Хмельницкий.
24 апреля 2003

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


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

SW soft NIX
ID = 3.237.200.21