만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

가상 현실 놀이 공간

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

요약
장애물이 있는 r by c 격자에서 빈칸으로 이루어진 극대 직사각형 중 한 변이 s 이상, 다른 변이 t 이상인 것의 개수를 셉니다.
난이도

보통10점 중 7점

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

문제

Yolanda는 집 안의 가구 배치를 막 마쳤다. 그녀의 집은 한 변의 길이가 rr과 cc인 직사각형이다. Yolanda는 가상 현실(VR) 놀이 공간을 놓을 자리를 고르려 한다.

VR 놀이 공간은 다음 조건을 따라야 한다.

  • 모양은 직사각형이다.
  • 변은 집의 변과 평행하고 수직이다.
  • 차지하는 단위 정사각형은 그 전체를 정확히 덮는다.
  • 장애물을 포함하지 않는다.
  • 한쪽 방향으로 ss 단위 이상, 다른 방향으로 tt 단위 이상이어야 한다.
  • 각 변은 집의 외벽이나 장애물에 닿아 있다. 다시 말해, VR 놀이 공간은 최대 크기다.

집의 지도가 주어졌을 때, Yolanda가 VR 놀이 공간을 놓을 수 있는 서로 다른 자리의 수를 구하라.

입력

첫 줄에 정수 rr, cc, ss, tt (1≤r,c,s,t≤30001 \le r, c, s, t \le 3000)가 주어진다. 각각 집의 길이와 너비, 그리고 VR 놀이 공간의 크기다. 다음 rr개 줄에는 집을 나타내는 길이 cc의 문자열이 한 줄씩 주어진다. 각 문자는 빈 단위 정사각형을 뜻하는 점(.)이거나 장애물을 뜻하는 숫자 0(0)이다.

출력

정수 하나를 출력한다. Yolanda가 VR 놀이 공간을 놓을 수 있는 서로 다른 자리의 수다.

예제1

  1. 예제 1

    입력
    4 7 1 2
.....00
.0...0.
..00.0.
.0.0.00
    예상 출력
    6