#2419 위성 영상 분석

1 s   128 MB  

Description

W x H(가로 x 세로) 의 크기로 입력되는 위성 영상이 바다와 육지로만 구별된다고 할 경우, 연결된 육지의 개수가 몇 개이며, 가장 넓은 육지의 면적이 얼마인지를 찾는 프로그램을 작성하시오. 위성 영상은 ‘.’과 ‘*’로만 이루어져 있으며 ‘.’은 바다를 의미하고, ‘*’은 육지를 의미한다. 육지가 연결되어 있다는 의미는 가로, 세로 방향으로만 ‘*’이 이어져 있다는 것을 의미한다(대각선 방향으로 이어진 ‘*’은 연결되지 않은 것으로 본다). 면적은 ‘*’ 하나당 1로 계산하므로 연결된 육지 영역의 ‘*’ 개수와 같은 값으로 간주한다

. ..*.....**

.**..*****

.*...*....

..****.***

..****.***

예를 들어 위의 그림과 같이 위성 영상이 입력된다고 하면 육지의 개수는 3개이며, 가장 넓은 육지의 면적은 16이다.

Input

첫 줄에는 테스트 케이스의 수 $T$가 입력된다$(1 \leq T \leq 10)$.

그 다음 줄부터 테스트 케이스 수만큼 대해 위성 영상의 크기 $W, H(1 \leq W, H \leq 50)$가 입력되고

그 다음 줄부터 $W * H$ 크기의 위성 영상 데이터가 주어진다.

Output

테스트 케이스 별로 연결된 육지의 개수와 가장 넓은 육지의 면적을 한 줄씩 출력한다.

Sample Input

Sample Output

1
10 5
..*.....**
.**..*****
.*...*....
..****.***
..****.***
3 16

Source

동의대학교 멀티미디공학과 우영운(2015년 6월 18일)