Problem K
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.
Input
Input contains a sequence of maps, each given as a rectangular array of characters (at most 80 by 80). There is one blank line between each pair of maps. Input ends at end of file.
All maps contain only the characters dot (.), X, #, and B. Dots represent ocean water. X’s and #’s represent island land. B’s represents bridges, and each X represents the land that is the endpoint of one or more bridges.
Each map contains 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 0 or more horizontal or vertical bridges. Each bridge has at least one B, and connects only the two islands at its two endpoints. Bridges do not cross each other or extend over the # land of an island.
Output
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.
| Sample Input 1 | Sample Output 1 |
|---|---|
.................... .................... .....###............ .....##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 |
