집들이
시간 제한1초메모리 제한128 MB
막힌 칸이 있는 격자에서 빈 칸으로만 이루어진 가장 큰 직사각형을 찾아 그 둘레(가로+세로의 2배)를 구하는 문제입니다.
문제
상근이는 오랫동안 모은 돈으로 아파트를 샀고, 가능한 한 많은 친구를 초대해 집들이를 하려고 한다.
집들이 전에 모든 사람이 둘러앉을 수 있는 직사각형 식탁 하나를 사려 한다. 식탁에 앉을 수 있는 사람 수는 식탁 네 변의 길이 합과 같다.
식탁은 항상 아파트의 변과 평행하게 놓아야 하며, 식탁이 차지하는 영역은 모두 빈 칸 안에 있어야 한다.
아파트의 배치가 주어졌을 때, 상근이가 초대할 수 있는 사람 수의 최댓값을 구하시오.
입력
첫째 줄에 아파트의 크기 R과 C가 주어진다. (1 <= R, C <= 400)
다음 R개 줄에는 길이 C의 문자열이 하나씩 주어진다. 빈 칸은 ., 막힌 칸은 X로 주어진다.
식탁은 오직 빈 칸에만 놓을 수 있다. 사람의 크기는 매우 작다고 생각한다.
출력
상근이가 초대할 수 있는 사람 수의 최댓값을 출력한다.