Cinema
Национална Олимпиада по Информатика 2011, Кръг 1
Time Limit: 0.2s, Memory Limit: 64MiB
На пръв поглед лесна задача, изборът на места в киното не винаги е толкова тривиален. Например за да гарантира определена интимност с приятеля си по време на някоя прожекция, Елеонора е решила да избере местата по такъв начин, че да се намират в някакъв правоъгълник от незаети седалки. Вие решавате да й помогнете, като напишете програма, която намира колко възможности за това има тя.

На Вашата програма ще бъде подаден размерът на кинозалата – N реда с по M седалки и изискваните от Ели размери на „свободния” правоъгълник – поне R реда с поне C седалки на ред. Изчислите колко (евентуално припокриващи се) такива правоъгълници има.
Вход
На първият ред от стандартния вход ще бъдат дадени две цели числа N и M – броят редове и колони на кинозалата. На втория ред ще бъдат зададени други две цели числа R и C – броя редове и колони, които Ели желае за „празен” правоъгълник. Следват N реда с по M символа, всеки от които е '.', означаващ празна седалка или '#', означаващ заета такава.
Изход
На единствен ред на стандартния изход изведете едно цяло число – броят правоъгълници с размер R на C, които могат да бъдат разположени върху незаети седалки.
Ограничения
  • 1 ≤ RN ≤ 1,000
  • 1 ≤ CM ≤ 1,000
Примерен Вход Примерен Изход
8 13 3 5 ..#...#....#. #............ ......#...... #............ ..#......#... ...#.....#... ......#...... ......#...... 4
Кинозалата има 8 реда и 13 колони. Ели изисква правоъгълникът, в който седят, да има поне 3 реда и 5 колони. Има 4 различни правоъгълника, които изпълняват това условие и техните горни леви ъгли са с координати (2, 2), (2, 8), (2, 9), (4, 5), където координатите са (ред, колона). Забележете, че правоъгълниците не бива да бъдат ротирани по какъвто и да е начин.
Мрън!