레이팅 미적용설명
농부 존(Farmer John)의 소들은 최근 흠집이 여러 군데 있는 큰 대리석 판을 받았다. 대리석 판을 N x N 정사각형 격자 (5 <= N <= 300)로 표현하는데, '*'는 흠집을, '.'는 흠 없는 부분을 나타낸다.
소들은 이 대리석 판에 숫자 "8"을 조각하고 싶어 한다. 유효한 8자는 다음 성질을 가진다.
- 8자는 위와 아래, 두 개의 직사각형으로 이루어진다.
- 위와 아래 직사각형 모두 내부에 적어도 한 칸이 있다.
- 위 직사각형의 아래 변은 아래 직사각형의 위 변의 (진부분집합일 필요는 없는) 부분집합이다.
- 8자는 대리석 판의 흠 없는 영역에만 조각할 수 있다.
8자의 미적 점수는 두 직사각형이 둘러싸는 넓이의 곱과 같다. 소들은 이 점수를 최대화하고 싶어 한다.
제약
입력 형식
첫째 줄: 대리석 판의 한 변의 길이를 나타내는 정수 N.
둘째 줄부터 N+1번째 줄까지: 각 줄은 대리석 판의 한 행을 설명하며, '*'(흠집) 또는 '.'(흠 없는 부분)인 N개의 문자로 이루어져 있다.
출력 형식
대리석 판의 흠집 칸을 전혀 사용하지 않는 8자의 최고 미적 점수. 8자를 만들 수 없으면 -1을 출력한다.
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:
입력을 읽을 파일
eight.in · 출력을 쓸 파일 eight.out예제 1
입력
15
...............
...............
...*******.....
.*....*.......*
.*......*....*.
....*..........
...*...****....
...............
..**.*..*..*...
...*...**.*....
*..*...*.......
...............
.....*..*......
.........*.....
...............출력
3888설명
Output details: The top rectangle has area 6x9=54 and the bottom 12x6=72, giving score 54x72=3888.
문제 정보
태그