별 세기

면접 대비

시간 제한2초메모리 제한1024 MB

요약

흑백 비트맵에서 상하좌우로 인접한 흰 픽셀 덩어리의 개수를 센다.

난이도: 쉬움10점 중 3점
유형: 그래프, DFS, BFS, 행렬
정답자: 아직 제출이 없습니다

문제

천문학은 컴퓨터 기술을 활용하면서 크게 발전했다. 알고리즘은 밤하늘을 찍은 디지털 이미지를 자동으로 분석해 새로운 패턴을 찾아낼 수 있다.

이 문제에서는 비트맵 이미지에 보이는 별의 개수를 세는 분석 프로그램을 작성한다. 이미지는 픽셀로 이루어지며, 각 픽셀은 검은색 또는 흰색이다. 검은색은 #, 흰색은 -로 나타낸다. 검은색 픽셀은 모두 하늘의 일부로, 흰색 픽셀은 각각 별의 일부로 본다. 세로 또는 가로로 인접한 흰색 픽셀은 같은 별에 속한다.

입력

각 테스트 케이스의 첫 줄에는 두 정수 1 ≤ m, n ≤ 100이 주어진다. 이어서 m개의 줄이 주어지며, 각 줄에는 정확히 n개의 픽셀이 들어 있다.

출력

각 테스트 케이스마다 케이스 번호와 해당 이미지에 보이는 별의 개수를 출력한다. 출력 형식은 아래 예시와 같다.

예제1

예제 1

입력

10 20
#################---
##-###############--
#---################
##-#################
########---#########
#######-----########
########---#########
##################--
#################---
##################-#
3 10
#-########
----------
#-########

예상 출력

Case 1: 4
Case 2: 1