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