베시의 식사 시간

면접 대비

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

요약

가로 W, 세로 H 격자에서 잔디 칸과 바위 칸이 주어질 때, 8방향으로 연결된 잔디 영역 중 가장 큰 영역의 칸 수를 구한다.

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

문제

소 베시의 밥 먹을 시간이 되었습니다. 농부는 베시를 어느 목초지에 둘지 정하려고 합니다. 농장은 $W \times H$ 크기의 격자로 이루어져 있으며 ( $1 \le W \le 750$ , $1 \le H \le 750$ ), 크고 작은 바위들에 의해 하나 이상의 서로 떨어진 목초지로 나뉩니다. 각 칸은 풀 또는 바위입니다.

베시는 먹성이 좋아서 풀을 계속 뜯어 먹고 싶어 합니다. 베시는 어떤 칸에서 가로, 세로, 또는 대각선으로 인접한 칸으로 이동할 수 있습니다(즉, 여덟 방향으로 이동합니다). 베시는 발이 아프기 때문에 바위 칸을 지날 수 없고, 농장 밖으로 나갈 수도 없습니다. 베시가 한 번의 식사에서 뜯어 먹을 수 있는 풀 칸의 최대 개수를 구하세요.

지도에서 . 는 풀 칸을, * 는 바위 칸을 나타냅니다. 아래는 $10 \times 8$ 크기의 지도 예시와 그 지도가 나뉘는 세 목초지를 자세히 표시한 그림입니다(각 목초지를 숫자 1, 2, 3 으로 표시).

      ...*....**  |  111*....**   ...*2222**    ...*....**
      ..**....**  |  11**....**   ..**2222**    ..**....**
      ...*....**  |  111*....**   ...*2222**    ...*....**
      ...**.*.**  |  111**.*.**   ...**2*2**    ...**.*.**
      ***.**.***  |  ***1**.***   ***.**2***    ***.**.***
      ...**.*.**  |  111**.*.**   ...**2*2**    ...**.*.**
      ...*.*****  |  111*.*****   ...*2*****    ...*.*****
      ...***..**  |  111***..**   ...***..**    ...***33**

목초지 1은 21칸, 목초지 2는 18칸, 목초지 3은 2칸입니다. 따라서 베시는 21칸짜리 목초지 1을 선택해야 가장 많은 풀을 먹을 수 있습니다.

하나의 목초지란 서로 여덟 방향으로 연결된 풀 칸들의 최대 집합을 뜻합니다. 가장 큰 목초지의 풀 칸 개수를 출력하세요.

입력

첫째 줄: 공백으로 구분된 두 정수 $W$ 와 $H$
둘째 줄부터 $H+1$ 번째 줄까지: $i+1$ 번째 줄은 $i$ 번 행을 나타내며, 공백 없이 $W$ 개의 문자로 이루어집니다. 각 문자는 .(풀) 또는 *(바위)입니다.

출력

첫째 줄: 베시가 한 목초지에서 뜯어 먹을 수 있는 풀 칸의 최대 개수를 나타내는 정수 하나.

예제6

예제 1

입력

10 8
...*....**
..**....**
...*....**
...**.*.**
***.**.***
...**.*.**
...*.*****
...***..**

예상 출력

예제 2
입력
```
1 1
.
```
예상 출력
```
1
```
예제 3
입력
```
1 1
*
```
예상 출력
```
0
```
예제 4
입력
```
3 3
...
...
...
```
예상 출력
```
9
```
예제 5
입력
```
2 2
.*
*.
```
예상 출력
```
2
```
예제 6
입력
```
5 1
.*.*.
```
예상 출력
```
1
```