음메 요새
시간 제한2초메모리 제한512 MB
테두리 칸이 모두 잔디인 직사각형 중에서 내부 넓이가 가장 큰 값을 구합니다.
문제
베시는 친구 엘시와 함께 요새를 짓는다. 좋은 요새가 다 그렇듯 이 요새도 튼튼한 뼈대에서 시작해야 한다. 베시는 폭이 1미터인 직사각형 테두리 모양으로 뼈대를 세우고, 그 위에 요새를 올릴 생각이다.
부지는 이미 정해 두었다. 세로 미터, 가로 미터인 땅이고 이다. 그런데 이 땅에는 늪지가 섞여 있어서 뼈대를 받칠 수 없는 칸이 있다. 뼈대가 늪지 칸을 하나도 밟지 않도록 놓을 때, 요새가 덮는 넓이, 즉 뼈대가 둘러싼 직사각형의 넓이의 최댓값을 구하라.
직사각형은 만큼 작아도 된다. 테두리에 놓이는 칸만 잔디이면 되고, 내부 칸은 늪지여도 상관없다.
입력
첫 줄에 정수 과 이 주어진다.
다음 개의 줄에는 각각 문자 개가 주어져 부지를 나타낸다. '.'은 평범한 잔디, 'X'는 늪지다.
출력
베시가 요새로 덮을 수 있는 최대 넓이를 정수 하나로 출력한다. 뼈대를 어디에도 놓을 수 없으면 0을 출력한다.
힌트
첫 번째 예제에서 최적인 뼈대 위치를 'f'로 표시하면 다음과 같다.
.ffff.
.fX.fX
Xf.Xf.
.ffff.
..X...