Флаги
(Время: 2 сек. Память: 128 Мб Сложность: 58%)
У Васи есть ткань прямоугольной формы, которая имеет клетчатую структуру и состоит из N×M цветных частей, разбитых на N строк и M столбцов.
Как известно, Вася интересуется флагами стран и он заметил, что если вырезать из этой ткани прямоугольник, состоящий из трёх цветных полос, то он будет напоминать флаг какой-нибудь страны. Вася думает, что прямоугольник похож на флаг, если он состоит из трёх одноцветных полос одинаковой высоты, находящихся друг под другом. При этом цвет средней полосы не должен совпадать с цветом верхней и нижней полос.
Вася решил вырезать флаг по линиям сетки и при этом решил, что не будет его поворачивать. И тут его заинтересовал вопрос: а сколько существует способов вырезать такой флаг? Будем считать, что прямоугольники, образующие одинаковые флаги и расположенные в разных местах, считаются различными.
Помогите Васе вычислить количество различных флагов, которые могут у него получиться.
Примеры прямоугольников, являющихся флагами:
Примеры прямоугольников, не являющихся флагами:
Входные данные
Первая строка входного файла INPUT.TXT содержит два целых числа N и M (1 ≤ N, M ≤ 2000) – количество строк и столбцов в материи.
Каждая из последующих N строк входных данных описывает очередную строку материи и состоит из M строчных английских букв от «a» до «z», где одинаковым цветам соответствуют одинаковые буквы, а разным цветам – разные буквы.
Выходные данные
В выходной файл OUTPUT.TXT выведите одно целое число – количество флагов, которые могут получиться у Васи.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4 3
aaa
bbb
ccb
ddd | 6 |
Пояснение к примеру
Выделенные прямоугольники на следующем изображении обозначают все возможные флаги, которые можно получить:
Система оценки
Решения, работающие только для N, M ≤ 10, будут оцениваться в 16 баллов.
Решения, работающие только для N, M ≤ 100, будут оцениваться в 32 балла.
Решения, работающие только для N, M ≤ 400, будут оцениваться в 52 балла.
Решения, работающие только для N, M ≤ 1000, будут оцениваться в 80 баллов.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
