COUNTISL - How many Islands
You are given a simple map of an archipelago. Can you determine how many islands it shows?
The map consists of grid squares with characters, where '#' indicates land and '.' indicates water. Two land squares belong to the same island if they are neighbouring grid squares, which means their x coordinates and y coordinates differ by at most 1.
Input
The first line of the input contains a number T ≤ 20 which indicates the number of test cases to follow.
Each test case starts with a line containing two numbers n and m (1 ≤ n,m ≤ 200), the number of rows and the number of columns of the grid, respectively. The following n lines contain m characters each and describe the map to be processed. You may assume that the map contains only characters '#' and '.', and that the border of the map consists only of water (character '.').
Output
For each test case print in a line the number of islands shown on the corresponding map in the input.
Example
Input: 2 1 1 . 6 4 .... ..#. .#.. .... .##. .... Output: 0 2
hide comments
otoya:
2024-01-26 01:53:50
s1mple dfs
|
|
boominggem:
2022-12-05 17:04:20
i need hints :(
|
|
saketag007:
2018-09-18 22:41:12
Nice problem , AC in one go , 0.01s |
|
learnerfirst:
2015-08-15 21:20:12
Getting NZEC. Java Code works on my system until the size 194*194, throws stackflowerror for anything above that. Is there any SUCCESSFUL submission in JAVA for this problem? |
|
uptoyou:
2015-07-04 10:09:21
dfs :)) |
|
innovolt:
2014-04-11 22:01:03
1 more dfs applic. |
|
Harsh Thakar:
2011-10-16 07:41:21
Getting WA. Some more test cases please |
Added by: | Adrian Kuegel |
Date: | 2007-01-29 |
Time limit: | 3.087s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |