Островная Грузовая Пассажирская Компания планирует предоставить автобусное сообщение для ряда островных государств Южного Океана. Каждое государство состоит из нескольких островов, некоторые из которых связаны мостами. Чтобы сэкономить средства, компания хочет использовать наименьшее количество автобусов. Каждый остров должен иметь доступ к автобусу, но компания будет использовать только один автобус для любой группы из двух или более островов, которые соединены мостами.
Ваша задача - написать программу, которая, учитывая карту островной страны, вычисляет количество островов, мостов и наименьшее количество автобусов, необходимых для этой страны.
Ввод состоит из нескольких тестов. Тесты отделены друг от друга пустой строкой. Каждый тест представляет из себя прямоугольную карту. Карта состоит из нескольких строк одинаковой длины, содержащих символы .(точка), X, #, и B. Максимальный размер карты - 80 на 80.
Точки обозначают океан, X и # - островные клетки, B - мосты. Каждый символ X обозначает конец одного или нескольких мостов.
Каждая карта содержит 1 или более прямогульных островов. Различные острова не имеют общих по стороне клеток.
Каждая карта содержит 0 или более горизонтальных или вертикальных мостов. Каждый мост содержит хотя бы один символ B в своем описании и соединяет ровно 2 острова. Мосты не пересекают друг друга и не продолжаются над клетками #. Символ B не может быть соседним с символом B или X кроме как в случае, когда когда они являются частью одного моста.
Для каждой карты выведите номер карты, количество островов на ней, количество мостов на ней и наименьшее требуемое количество автобусов. Следуйте формату из примеров. Выводите пустую строку между описаниями отдельных карт.
| Sample input | Sample Output |
|---|---|
.................... .................... .....###............ .....##XBBBBX....... .....###............ .................... .............###.... ....####............ ....####............ ....###XBBBBX....... .......B....#....... .......B....#....... .......B....X.##.... .......B....B.##.... ...####X####X#...... ...###########...... ...###########...... ...###########...... ...###########...... .................... ....######X###......##X##....... ..........B...........B......... .........#X###########X###...... ....... .#..... ..#.... ....##. ....##. ....... .##.... ...#... .....#. ....##... ....##... .#XBBBBX# .##....## |
Map 1 islands: 7 bridges: 4 buses needed: 4 Map 2 islands: 3 bridges: 2 buses needed: 1 Map 3 islands: 6 bridges: 0 buses needed: 6 Map 4 islands: 3 bridges: 1 buses needed: 2 |