Codeforces Round 154 (Div. 2) |
---|
Закончено |
Вася недавно начал изучать английский язык. Сейчас ему нужно выучить, как пишутся буквы латинского алфавита. Поскольку он еще не до конца запомнил некоторые из них, он решил немного потренироваться.
Он нашел клетчатый лист бумаги и начал писать на нем произвольные буквы латинского алфавита. В конце концов Вася написал n строк по m символов в каждой. Таким образом, он получил прямоугольную таблицу размера n × m, в каждой клетке которой была написана некоторая буква латинского алфавита. Пронумеруем строки этой таблицы сверху вниз целыми числами от 1 до n, а столбцы слева направо целыми числами от 1 до m.
После этого, взглянув на полученную прямоугольную таблицу, Вася заинтересовался следующим вопросом: сколько существует подтаблиц, для которых выполняются следующие два условия:
Формально, подтаблица определяется следующим образом. Она задается четырьмя целыми числами x1, y1, x2, y2 такими, что 1 ≤ x1 < x2 ≤ n, 1 ≤ y1 < y2 ≤ m. Тогда в подтаблице содержатся все такие клетки (x, y) (x — номер строки, y — номер столбца), для которых выполняются неравенства x1 ≤ x ≤ x2, y1 ≤ y ≤ y2. Угловыми клетками таблицы считаются клетки (x1, y1), (x1, y2), (x2, y1), (x2, y2).
Вася уже слишком устал, выписывая буквы на лист бумаги. Поэтому он просит Вас посчитать интересующую его величину.
В первой строке заданы три целых числа n, m, k (2 ≤ n, m ≤ 400; 0 ≤ k ≤ n·m).
Далее в n строках записано по m символов — заданная таблица. Каждый символ таблицы является строчной буквой латинского алфавита.
Выведите единственное число — требуемое количество подтаблиц.
3 4 4
aabb
baab
baab
2
4 5 1
ababa
ccaca
ccacb
cbabc
1
В первом примере имеется две искомые подтаблицы: первая имеет верхний левый угол в клетке (2, 2) и правый нижний угол в клетке (3, 3), вторая имеет верхний левый угол в клетке (2, 1) и правый нижний угол в клетке (3, 4).
Название |
---|