Предположим, вы ходите каждый день на занятия. Каждый раз вы приходите в последний момент, и некоторые места в классе уже заняты. Например, сегодня вы с друзьями пришли в класс и обнаружили, что некоторые места уже заняты.
В класс \(n\) рядов по \(m\) мест в каждом ряду. Таким образом, класс можно представить как матрицу \(n \times m\). Символ «.» означает свободное место, а символ «*» означает занятое место. Вам необходимо найти \(k\) соседних свободных мест в одном ряду или в одном столбце. Посчитайте количество способов выбрать места. Два способа считаются различными, если различны множества мест, которые вы выберете.
Первая строка содержит три различных целых числа \(n,m,k\) (\(1 \leq n, m, k \leq 2\,000\)), где \(n,m\) описывают размеры класса, а \(k\) — число соседних мест, которые вы должны найти.
Каждая из следующих \(n\) строк содержит \(m\) символов «.» или «*». Они образуют матрицу, описывающую класс, «.» обозначает свободное место, а «*» — занятое.
Выведите одно число — число способов выбрать \(k\) свободных мест в одном ряду или столбце.
В первом примере есть три способа выбрать места. Они перечислены ниже.
2 3 2 **. ...
3
1 2 2 ..
1
3 3 4 .*. *.* .*.
0
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач