#LQC20230104. 花坛

花坛

题目描述

小明有一张 NM(2N30,2M30)N * M (2 \le N \le 30, 2 \le M \le 30) 的方格纸,且每个小方格都是正方形,纸上的每个小方格中都画了植物,共有 aabbcc 三种不同的植物。为了美观现按照以下要求为植物涂色。
要求:
1)涂色的植物区域必须是一个正方形矩阵,最小为一个 222 * 2 的正方形矩阵;
2)正方形矩阵中的植物必须是同一种植物;
3)只要正方形矩阵四个顶点不重合就算作不同的正方形矩阵(有部分区域重叠或者大正方形矩阵包含小正方形矩阵,按不同的正方形矩阵计算)。
已知方格纸的行数 N(2N30)N (2 \le N \le 30) 和列数 M(2M30)M (2 \le M \le 30),及每个小正方形方格中植物的种类,请帮助小明计算出,按要求有多少个正方形矩阵需要涂色。
例如:N=4,M=5N = 4, M = 5,矩阵如下图:
image
其中有 33 个正方形矩阵需要涂抹颜料(蓝色框区域和绿色框区域的矩阵部分重叠按 22 个计算)。

输入规则

第一行输入两个正整数 N(2N30)N (2 \le N \le 30)M(2M30)M (2 \le M \le 30)NN 表示矩阵方格的行数,MM 表示矩阵方格的列数,两个正整数之间以一个空格隔开
第二行开始输入 NN 行,每行 MM 个字符(字符只包含aabbcc),字符之间以一个空格隔开

输出规则

输出一个整数,表示 NMN * M 的方格纸中,需要涂抹颜料的正方形矩阵的个数

样例

输入样例 #1

4 5
b b c a a
b b b c b
c c a a a
a b a a a

输出样例 #1

3