아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

카펫

시간 제한4초메모리 제한256 MB

요약
결함 표시를 최대 하나만 포함한 가장 넓은 직사각형 조각 넓이를 구합니다.
난이도

보통10점 중 7점

유형
스택, 누적 합, 행렬
정답자
아직 제출이 없습니다

문제

바이타자르가 가게에서 카펫을 살펴보고 있다. 카펫 곳곳에는 보기 흉한 제조 결함이 있다. 그래도 카펫을 최대한 넓게 사고 싶어서, 결함이 한 개까지 있는 카펫은 사기로 했다. 결함이 있는 자리에는 큰 화분을 놓으면 되니 상관없다.

가게에 있는 카펫은 높이가 ww이고 너비가 ss인 직사각형이며, 1×11 \times 1 크기의 정사각형 w×sw \times s개로 나뉘어 있다. 각 정사각형에 결함이 있는지 없는지는 모두 알고 있다. 바이타자르는 이 정사각형으로 이루어진 직사각형 조각 중에서 결함이 있는 정사각형을 최대 한 개만 포함하는 가장 넓은 조각을 사려고 한다. 그 조각의 넓이를 구하여라.

입력

첫째 줄에 카펫의 높이 ww와 너비 ss가 주어진다 (1≤w,s≤20001 \le w, s \le 2000). 다음 ww개 줄에는 카펫의 각 행이 위에서부터 차례로 주어진다. 각 줄은 길이가 ss인 문자열이고, .은 결함이 없는 정사각형, #은 결함이 있는 정사각형을 뜻한다.

출력

정사각형으로 이루어지고 결함이 있는 정사각형을 최대 한 개 포함하는 직사각형 조각의 최대 넓이를 한 줄에 출력한다.

예제6

  1. 예제 1

    입력
    4 5
    #.#..
    ....#
    ..#..
    ....#
    
    예상 출력
    12
    
  2. 예제 2

    입력
    1 1
    .
    
    예상 출력
    1
    
  3. 예제 3

    입력
    1 1
    #
    
    예상 출력
    1
    
  4. 예제 4

    입력
    3 4
    ....
    ....
    ....
    
    예상 출력
    12
    
  5. 예제 5

    입력
    1 10
    ..#....#..
    
    예상 출력
    7
    
  6. 예제 6

    입력
    5 5
    .....
    .....
    ..#..
    .....
    .....
    
    예상 출력
    25