eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Island Buses

Island Buses

The Island Cargo and Passenger Company is planning to provide bus service for a number of South Pacific island nations. Each nation consists of a collection of islands, some of which are connected by bridges. To save costs, the company wants to use the fewest number of buses possible. Every island must have access to a bus, but the company will only use one bus for any group of two or more islands that is connected by bridges. Your job is to write a program which, given a map of the island nation, computes the number of islands, bridges, and the smallest number of buses needed for that country. \InputFile Input contains a sequence of maps, each given as a rectangular array of characters (at most \textbf{80} by \textbf{80}). There is one blank line between each pair of maps. Input ends at end of file. All maps contain only the characters dot (\textbf{.}), \textbf{X}, \textbf{#}, and \textbf{B}. Dots represent ocean water. \textbf{X}'s and \textbf{#}'s represent island land. \textbf{B}'s represents bridges, and each \textbf{X} represents the land that is the endpoint of one or more bridges. Each map contains \textbf{1} or more rectangular islands. Different islands are not adjacent vertically or horizontally. Diagonal adjacency is not enough to drive a bus across. Each map contains \textbf{0} or more horizontal or vertical bridges. Each bridge has at least one \textbf{B}, and connects only the two islands at its two endpoints. Bridges do not cross each other or extend over the \textbf{#} land of an island. No \textbf{B} may be adjacent to another \textbf{B} or \textbf{X} unless they are part of the same bridge. \OutputFile For each map you should print the map number, followed by lines giving the number of islands, bridges, and buses needed. Print a blank line between each pair of map outputs. Follow the format of the sample output.
Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные #1
....................
....................
.....###............
.....##XBBBBX.......
.....###............
....................
.............###....
....####............
....####............
....###XBBBBX.......
.......B....#.......
.......B....#.......
.......B....X.##....
.......B....B.##....
...####X####X#......
...###########......
...###########......
...###########......
...###########......
....................

....######X###......##X##.......
..........B...........B.........
.........#X###########X###......

.......
.#.....
..#....
....##.
....##.
.......
.##....
...#...
.....#.

....##...
....##...
.#XBBBBX#
.##....##
Выходные данные #1
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
Источник 2013 ACM-ICPC North American Qualification Contest