실행 시간 제한 | 메모리 제한 |
---|---|
2 초 | 512 MB |
소영이는 친구 지원과 함께 요새를 짓고 있습니다. 좋은 요새를 짓기 위해 견고한 뼈대가 있어야 합니다. 소영이는 1미터 너비의 직사각형 형태의 뼈대를 만들고자 합니다. 그 위에 요새를 지을 것입니다.
이미 소영이는 요새를 짓기 위한 부지를 가지고 있습니다. 이 부지는 미터 x 미터의 크기입니다(). 하지만 부지 안에는 습지 지역이 포함되어 있어 뼈대를 지탱할 수 없는 부분이 있습니다. 습지를 피해서 뼈대를 세울 수 있는 최대 면적을 구해주세요.
첫 번째 줄에는 정수 과 이 있습니다.
다음 줄 각각에는 개의 문자가 있으며, 부지를 설명하는 격자를 형성합니다. '.' 문자는 일반 풀을 나타내며, 'X' 문자는 습지 지역을 나타냅니다.
소영이의 요새로 덮을 수 있는 최대 면적을 나타내는 한 개의 정수를 출력합니다.
5 6 ...... ..X..X X..X.. ...... ..X...
16
예제에서 최적의 배치는 아래의 'f'들로 표시됩니다:
.ffff.
.fX.fX
Xf.Xf.
.ffff.
..X...
출처: USACO 2016 January Contest, Platinum Problem 1. Fort Moo