Input File: cartin.txt
Output File: cartout.txt
Time Limit: 0.333 second
You have been contracted by a company which is mapping Pacific islands. They have been taking photographs of the islands from aircraft to produce their maps. The photographs have been converted to grids showing where land is present and where there is water.
You have been called in to help the map makers count the number of islands in their photos. This task is complicated by the fact that some of the islands have lakes and lagoons, which show up as water in the photographs. For example, consider the photograph
..X..XX. .XX..X.X .X...X.X .XX..XXX ....X..X ...XXX.. ...X.X.. XX.XXX..
in which an
X denotes land and a
denotes water. This photograph
contains four islands - they have been designated
D in the diagram below:
..A..BB. .AA..B.B .A...B.B .AA..BBB ....C..B ...CCC.. ...C.C.. DD.CCC..
Note that two land squares in the grid are considered adjacent if they share an edge horizontally or vertically (not diagonally). Two land squares are part of the same island if they can be reached from one another via a sequence of adjacent land squares.
In the event an island contains a lake which contains an island, the two islands are counted as separate islands. For example, the map
.XXXXXX. .X....X. .X.XX.X. .X.XX.X. .X.XX.X. .X....X. .XXXXXX. ........
contains two islands.
Your task is to read a map as input, and produce as output the number of islands contained in the map.
The input consists of a line containing two positive integers
h w, giving
the height and width of the map. Each of h and w is less
than or equal
to 100. Following this are h lines of input, each containing
exactly w characters, each character being an
Other than the space separating the integers h and w on the first line of input, there shall be no other space characters in the input file.
The output shall consist of a single integer n on a line giving the number of islands contained in the map.
3 5 ...XX X.X.X X.XXX
8 8 ..X..XX. .XX..X.X .X...X.X .XX..XXX ....X..X ...XXX.. ...X.X.. XX.XXX..
Your program will receive 100% for giving the correct number of islands as output. Any other output will receive 0%.