레이팅 미적용설명
베시는 친구 엘시와 함께 요새를 짓고 있다. 어떤 훌륭한 요새든 그렇듯, 이 요새도 튼튼한 뼈대에서 시작해야 한다. 베시는 폭 1미터의 직사각형 윤곽 모양의 뼈대를 만들고, 그 위에 요새를 지으려 한다.
베시는 이미 요새를 지을 부지를 골랐다. \(N\)미터 \(\times\) \(M\)미터 크기의 땅이다 (\(1 \leq N, M \leq 200\)). 안타깝게도 부지에는 뼈대를 지탱할 수 없는 늪지대가 몇 군데 있다. 뼈대가 늪지 위에 놓이지 않도록 하면서 요새로 덮을 수 있는 최대 넓이(뼈대가 지탱하는 직사각형의 넓이)를 구하도록 베시를 도와주자.
출제자: Nathan Pinsker
제약
출제자: Nathan Pinsker
입력 형식
첫째 줄에 정수 \(N\)과 \(M\)이 주어진다.
다음 \(N\)개의 줄에 각각 \(M\)개의 문자가 주어져 부지를 나타내는 격자를 이룬다. 문자 '.'은 보통 잔디를, 'X'는 늪지를 나타낸다.
출력 형식
베시가 요새로 덮을 수 있는 최대 넓이를 나타내는 하나의 정수를 출력한다.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
fortmoo.in · 출력을 쓸 파일 fortmoo.out예제 1
입력
5 6
......
..X..X
X..X..
......
..X...출력
16설명
In the example, the placement of the optimal frame is indicated by 'f's below:
.ffff.
.fX.fX
Xf.Xf.
.ffff.
..X...
문제 정보
riseoj 작성
출처 올림피아드 > USACO > 2015-2016 > January > Platinum
태그