만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

호텔

면접 대비

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

요약
파란 칸은 복도, 빨간 칸은 방으로 표시된 평면도에서 가장 큰 방의 넓이를 구합니다. 방이 없으면 -1을 출력합니다.
난이도

쉬움10점 중 3점

유형
행렬, 구현, 완전 탐색
정답자
아직 제출이 없습니다

문제

파벨은 어릴 때부터 건축가가 되는 것을 꿈꿨다. 그는 종이 위에 건물 도면을 자주 그렸고, 탁자나 벽에 그리기도 했다. 지금은 대학 학위를 받았고 유명한 건축가가 되었다.

어느 날 파벨은 어릴 적 그림을 뒤지다가 호텔 층의 평면도를 발견했다. 이 층은 n×mn \times m 미터 크기의 직사각형이다. 평면도의 각 칸은 층의 1제곱미터에 해당하며 파란색 또는 빨간색으로 칠해져 있다. 파벨은 파란색이 복도, 빨간색이 호텔 객실을 뜻한다는 것을 알아챘다.

파벨은 어릴 때부터 국제 기준을 지키려고 했다. 이 기준에 따르면 호텔 객실은 반드시 직사각형이어야 하므로, 평면도에서는 빨간색으로 채워진 직사각형으로 나타난다. 객실의 변은 층의 경계와 평행하다. 또한 모든 객실의 각 변을 따라 항상 복도가 있다.

화재 안전 규정에 따라 층의 가장자리에는 복도가 있어야 한다. 그래서 평면도의 첫 번째 행과 마지막 행, 첫 번째 열과 마지막 열은 모두 파란색이다.

파벨은 자신의 평면도에서 호텔 객실 넓이의 최댓값이 얼마인지 알고 싶어 한다. 이 넓이를 구하는 프로그램을 작성하라.

입력

첫 줄에 두 정수 nn과 mm (3≤n,m≤303 \le n, m \le 30)이 주어진다. 다음 nn개의 줄에는 각각 mm개의 문자가 주어진다. 문자 "*"는 파란색 칸(복도 1제곱미터)을, 문자 "."는 빨간색 칸(객실 1제곱미터)을 나타낸다.

출력

첫 줄에 가장 넓은 호텔 객실의 넓이를 출력한다. 평면도에 객실이 하나도 없으면 "-1"을 출력한다.

예제3

  1. 예제 1

    입력
    5 5
    *****
    *.***
    **..*
    **..*
    *****
    
    예상 출력
    4
    
  2. 예제 2

    입력
    4 5
    *****
    *.***
    *.*.*
    *****
    
    예상 출력
    2
    
  3. 예제 3

    입력
    3 3
    ***
    ***
    ***
    
    예상 출력
    -1