Задача №1390. Симпатичные прямоугольники
Знаменитый художник Вася только что закончил работу над своим новым шедевром и хочет знать, сколько он сможет получить за свой труд.
Картина представляет собой прямоугольник N на M сантиметров, разделенный на маленькие квадратики 1 на 1 сантиметр со сторонами, параллельными сторонам картины. Для достижения гармонии каждый из этих квадратиков Вася покрасил одним из 26 особых цветов, обозначаемых маленькими латинскими буквами.
Стоимость картины в точности равна количеству «симпатичных» частей в ней. Частью картины называется любой прямоугольник, который может быть вырезан из нее по границам квадратиков. Часть называется «симпатичной», если при выполнении симметрии относительно ее центра получается прямоугольник, раскрашенный также, как и исходная часть. Например, в картине, раскрашенной так:
abc
acb
симпатичными являются все части, состоящие из одного квадратика (их 6), а также части
bc и a
cb и a
Напишите программу, которая по информации о шедевре Васи определит его стоимость.
В первой строке содержатся два числа N и M (1 ≤ N, M ≤ 100). В следующих N строках идут строки, состоящие из M маленьких латинских символов. Символ в i-й строке j-м столбце определяет цвет соответствующего квадратика картины.
Выведите стоимость шедевра — количество частей, симметричных относительно своего центра.
Комментарии к примерам тестов
Этот пример разобран в условии
Симпатичными являются шесть частей 1x1, одна часть 1x2 и сама картина.
Частичные ограничения
Первая группа состоит из тестов, в которых N, M ≤ 15. Данная группа оценивается в 30 баллов.
Вторая группа состоит из тестов, в которых N, M ≤ 50. Данная группа оценивается в 30 баллов.
2 3 abc acb
8
3 2 ab cc ba
8