Under construction

Still being built. Things may change

Counting Stars

Interview

Time limit2sMemory limit1024 MB

Summary
Count the connected components of white pixels in a black-and-white bitmap, where adjacency is vertical or horizontal.
Level

Easy3 of 10

Topics
Graph, DFS, BFS, Matrix
Solved
No attempts yet

Problem

Astronomy has advanced greatly through the use of computer technology. Algorithms can automatically analyze digital images of the night sky and look for new patterns.

In this problem you write such an analysis program that counts the number of stars visible in a bitmap image. An image consists of pixels, and each pixel is either black or white. Black is written # and white is written -. Every black pixel is part of the sky, and every white pixel is part of a star. White pixels that are adjacent vertically or horizontally belong to the same star.

Input

Each test case begins with a line containing two integers 1 ≤ m, n ≤ 100. This is followed by m lines, each of which contains exactly n pixels.

Output

For each test case, print the case number followed by the number of stars visible in the corresponding image. Follow the format shown in the example below.

Examples1

  1. Example 1

    Input
    10 20
#################---
##-###############--
#---################
##-#################
########---#########
#######-----########
########---#########
##################--
#################---
##################-#
3 10
#-########
----------
#-########
    Expected output
    Case 1: 4
Case 2: 1