Virtual Reality Playspace

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

요약
장애물이 있는 격자에서 각 변이 벽이나 장애물에 닿고 두 변의 길이가 s, t 이상인 빈 직사각형의 개수를 센다.
난이도

어려움10점 중 8점

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

문제

Yolanda just finished moving the furniture around her house. Her house is shaped like a rectangle of side lengths rr and cc. Yolanda wants to choose a place to put her virtual reality (VR) playspace.

Yolanda has some standards for how a VR playspace should be positioned:

  • It should take the shape of a rectangle.
  • Its sides should be parallel and perpendicular to the sides of her house.
  • It must exactly cover the entirety of any unit square it occupies.
  • It should contain no obstacles.
  • It should be at least ss units across along one side, and at least tt units across along the other.
  • Each of its sides must border either the house’s outer walls, or obstacles. In other words, a VR playspace is maximally-sized.

Given a map of Yolanda’s house, Yolanda wants to know how many different places she can choose for her VR playspace.

입력

The first line of input contains four integers rr, cc, ss, and tt (1≤r,c,s,t≤3,0001 ≤ r, c, s, t ≤ 3\\, 000), giving the length and width of Yolanda’s house and the size of her VR playspace.

The next rr lines each contain a string of cc characters describing Yolanda’s house. Each character is either a dot (.) that denotes an empty square unit of space, or a zero (0) that denotes a square unit of obstacle.

출력

Output a single integer, the number of different places Yolanda can choose for her VR playspace.

예제1

  1. 예제 1

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