ascode.org discuss3

Description

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

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

Input

첫 줄에는 테스트 케이스의 수 T가 입력된다(1 <= T <= 10).
그 다음 줄부터 테스트 케이스 수만큼 대해 위성 영상의 크기 W, H(1 <= W, H <= 50)가 입력되고,
그 다음 줄부터 W * H 크기의 위성 영상 데이터가 주어진다.

Output

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

Sample Input Copy

1
10 5
..*.....**
.**..*****
.*...*....
..****.***
..****.***

Sample Output Copy

3 16

HINT

재귀 호출 활용 문제(grassfire algorithm)