Holes

면접 대비

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

요약

벽(#)과 빈 칸(.)으로 이루어진 격자에서 서로 연결된 빈 영역의 개수와 전체 빈 칸 수를 구한다.

난이도: 보통10점 중 4점
유형: 그래프, DFS
정답자: 아직 제출이 없습니다

문제

After receiving an impenetrable box, you wonder what’s inside! Write a program that finds out how many different disconnected sections the box has, and the total area of the space within the box.

입력

The first line will contain a single integer n that indicates the number of data sets that follow. Each data set will start with two integers r and c representing the number of rows and columns of the box, respectively. The next r lines will represent the box, with # representing walls and . representing spaces. The box will be surrounded entirely by walls.

출력

Output the number of discrete (disconnected) sections and the total number of spaces in the box, in the format shown in the example output.

예제1

예제 1

입력

2
4 8
########
#...#..#
#.#.#..#
########
3 3
###
#.#
###

예상 출력

2 sections, 9 spaces
1 section, 1 space