음메 요새

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

요약
테두리 칸이 모두 잔디인 직사각형 중에서 내부 넓이가 가장 큰 값을 구합니다.
난이도

보통10점 중 6점

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

문제

베시는 친구 엘시와 함께 요새를 짓는다. 좋은 요새가 다 그렇듯 이 요새도 튼튼한 뼈대에서 시작해야 한다. 베시는 폭이 1미터인 직사각형 테두리 모양으로 뼈대를 세우고, 그 위에 요새를 올릴 생각이다.

부지는 이미 정해 두었다. 세로 NN미터, 가로 MM미터인 땅이고 1≤N,M≤2001 \le N, M \le 200이다. 그런데 이 땅에는 늪지가 섞여 있어서 뼈대를 받칠 수 없는 칸이 있다. 뼈대가 늪지 칸을 하나도 밟지 않도록 놓을 때, 요새가 덮는 넓이, 즉 뼈대가 둘러싼 직사각형의 넓이의 최댓값을 구하라.

직사각형은 1×11 \times 1만큼 작아도 된다. 테두리에 놓이는 칸만 잔디이면 되고, 내부 칸은 늪지여도 상관없다.

입력

첫 줄에 정수 NN과 MM이 주어진다.

다음 NN개의 줄에는 각각 문자 MM개가 주어져 부지를 나타낸다. '.'은 평범한 잔디, 'X'는 늪지다.

출력

베시가 요새로 덮을 수 있는 최대 넓이를 정수 하나로 출력한다. 뼈대를 어디에도 놓을 수 없으면 0을 출력한다.

힌트

첫 번째 예제에서 최적인 뼈대 위치를 'f'로 표시하면 다음과 같다.

.ffff.
.fX.fX
Xf.Xf.
.ffff.
..X...

예제2

  1. 예제 1

    입력
    5 6
    ......
    ..X..X
    X..X..
    ......
    ..X...
    
    예상 출력
    16
    
  2. 예제 2

    입력
    1 1
    .
    
    예상 출력
    1