Archipelago lakes
Quido is studying lake ecology on a remote Pacific archipelago. One of the first tasks he has to do is to count the number of lakes on particular islands. He has made some satellite photos of the area. A typical photo contains some islands and there are often lakes on the islands. There may be lakes in which there are another small islands and on those smaller islands there may be further smaller lakes and in those lakes may still be other islands with lakes..., and so on.
Because of varying and also rising sea level the number of low lying lakes and lagoons may change with time. Therefore, repeated satellite photographing will be required from time to time in the future.
To avoid repetitive manual checks and recalculations of the number of the lakes, Quido decided to automatize the counting process.
 Image 1. Example of an archipelago photo. The colors have been preprocessed for easier viewing. The lake and island borderlines are part of the respective island landmasses, not of the sea or of a lake. The photo contains 19 archipelago islands. Ther are 4 lakes on the eastern big island, 3 lakes on the western big island, and no lakes on the other islands. |
The task
Find the number of all lakes on each archipelago island on a given salellite photo. Archipelago islands are those islands which are surrounded by the sea and not by a lake. On the other hand, each lake belongs to an archipelago island even when it is on an island which is surrounded by a lake.
Input
The input consists of more text lines. The first line contains two integers W and H, in this order, separated by space.
W represents the width of the picture in pixels and H represents the height of the picture in pixels.
Next there are H text lines, each line contains a string of length W. Each character in the string represents one image pixel.
The pixels representing water are coded by the dot character '.', and the pixels representing land are coded
by the capital X character 'X'.
When two land masses touch each other at a corner or at a side of one or more pixels they are considered to belong to the same island. The same rule holds for lakes and the surrounding sea: When two water masses touch each other at a corner or at a side of one or more pixels they are considered to belong to the same lake or to the see when at least one of the water masses is the sea.
No island in the photo touches the border of the photo, i.e all pixels along the border of the photo represent the sea.
The maximum size of the input photo is 2048×2048 pixels.
Output
The otuput contains one text line. The first value on the line is the number of archipelago islands. This value is followed by the list of number of lakes on particular archipelago islands. The list is sorted in non-increasing oreder. All output values are separated by spaces.
Example 1
Input20 6 .................... ..XXXXX..XXX.XXX..X. ..X.X.X..X.XXX.X..X. ..XXXXX..XX.X..X.... ..XX......XXXXXX..X. ....................Output
4 2 2 0 0
Example 2
Input9 9 ......... .XXXXXXX. .X.....X. .X.XXX.X. .X.X.X.X. .X.XXX.X. .X.....X. .XXXXXXX. .........Output
1 2
Example 3
Input83 18 ................................................................................... ..XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.. ..XX...........................................................................XX.. ..XX...........XX...XXXXX..XX.......XXXX...XX....XX..XXXXXX....XXXXX...........XX.. ..XX...........XX..XX......XX......XX..XX..XXX...XX..XX...XX..XX...............XX.. ..XX...........XX...XXXX...XX......XXXXXX..XX.XX.XX..XX...XX...XXXX............XX.. ..XX...........XX......XX..XX......XX..XX..XX...XXX..XX...XX......XX...........XX.. ..XX...........XX..XXXXX...XXXXXX..XX..XX..XX....XX..XXXXXX...XXXXX............XX.. ................................................................................... ................................................................................... ..XX....XXXX...XX....XX..XXXXXX.......XX.......XXXX...XX..XX..XXXXXX...XXXXX...XX.. ..XX...XX..XX..XXX...XX..XX...XX......XX......XX..XX..XX.XX...XX......XX.......XX.. ..XX...XXXXXX..XX.XX.XX..XX...XX......XX......XXXXXX..XXXX....XXXX.....XXXX....XX.. ..XX...XX..XX..XX...XXX..XX...XX......XX......XX..XX..XX.XX...XX..........XX...XX.. ..XX...XX..XX..XX....XX..XXXXXX.......XXXXXX..XX..XX..XX..XX..XXXXXX..XXXXX....XX.. ..XX...........................................................................XX.. ..XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.. ...................................................................................Output
17 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
Example 4
Input
The data represent the archipelago in the Image 1. They do not fit well to this the page and can be downloaded here.
19 4 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Public data
The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set