In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of April 14th
(this exercise will still be available for submission after that deadline, but without couting towards your grade)
[to understand the context of this problem, you should read the class #06 exercise sheet]
In this problem you should submit a complete program with the main function, reading with functions such as scanf and printing with functions such as printf.
Dr. Ross Geller is back in the lab (because paleontology was just too mainstream), and he's studying microbial growth in a Petri dish. His goal? Find the largest microbe colony before it spreads all over his workspace — and more importantly, before someone (cough, Joey) mistakes it for food.
The Petri dish can be thought of as a 2D grid, i.e. a matrix, where each cell may be either living microbe ('#') or an empty space ('.'). A microbe colony consists of connected '#' cells that are adjacent horizontally, vertically or diagonally.
For example, the following Petri dish has exactly three microbe colonies:
# | # | . | # | . | . | . |
. | # | # | # | . | . | . |
. | . | . | . | . | # | # |
. | # | . | . | . | # | # |
# | . | # | . | . | . | . |
The size of a colony is equal to the number of living microbes that make it up. In the picture above, the 3 colonies have size 6 (the yellow one), 3 (the blue one) and 4 (the green one). The largest colony is the one with the largest size, which in this case is the yellow colony.
Given the state of several cultures of microbes (indicated by a matrix of cells) your task is to find out the size of the largest microbe colony in each of them, i.e. the size of the largest connected set of living microbes in each case.
On the first line there is an integer N indicating the amount of cases to consider.
Each case starts with two numbers R and C indicating respectively the number of rows and columns of the petri dish. The R lines follow, each one with C characters, indicating the contents of each position: '.' for an empty position and '#' for a position with a living microbe.
The output should have N lines, each one with the size of the correspondent largest colony of microbes.
The following limits are guaranteed in all the test cases that will be given to your program:
1 ≤ N ≤ 20 | Number of test cases | |
1 ≤ R, C ≤ 100 | Dimensions of the matrix |
Example Input | Example Output |
2 5 7 ##.#... .###... .....## .#...## #.#.... 4 4 ##.# ...# #... ..#. |
6 2 |
Note: the first case is the one above in the figure. The second case has three colonies: two of size 2 (green and yellow) and two of size 1 (blue and orange). Therefore, the largest colony has size 2:
# | # | . | # |
. | . | . | # |
# | . | . | . |
. | . | # | . |