베시의 식사 시간

아직 제출이 없습니다시간 제한1초메모리 제한128 MB

문제

소 베시의 밥 먹을 시간이 되었습니다. 농부는 베시를 어느 목초지에 둘지 정하려고 합니다. 농장은 $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$개의 문자로 이루어집니다. 각 문자는 .(풀) 또는 *(바위)입니다.

출력

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