<PREV Problem:
NEXT>
Solved by 51 users: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Islands

Time limit = 1 second(s)

Memory limit = 33000 Kb

The scientists from Institute of Geodesy and Cartography made a satellite picture of some part of the Pacific Ocean. Then they composed a map of islands. But the map occurred quite large and they asked you for help. Do count a number of islands on the map.

Island is a set of square cells of land, where each cell is reachable from another by land. Each island is surrounded by water. No two islands contact by their corners. There are no lakes inside an island.

Input In the first line there are two space-separated numbers N and M — the hight and the width of a map ( 1 ≤ N, M ≤ 5000 ). Each of the next N lines contains M symbols describing the map: "~" stands for water, "*" stands for land.

Output The number of islands.

Input#1
7 6
~~~~~~
~*~**~
~***~~
~~~~~~
~*~~*~
~**~*~
~~~~~~
Output#1
3

Author:
Classical problem. Prepared by Semyonov Stanislav.
April 8, 2010

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 190ms

SW soft NIX
ID = 54.224.18.114