|Online MIPT programming contest||РУССКИЙ|
Time limit = 1 second(s)
Memory limit = 33000 KbThe 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.
7 6 ~~~~~~ ~*~**~ ~***~~ ~~~~~~ ~*~~*~ ~**~*~ ~~~~~~
Classical problem. Prepared by Semyonov Stanislav.
April 8, 2010
© acm.mipt DevGroup
The page was generated in 210ms