880081 - 花坛

小明有一张NM(2≤N≤30,2≤M≤30)的方格纸,且每个小方格都是正方形,纸上的每个小方格中都画了一个花朵,共有a、b、c三种不同的花朵。为了美观现按照以下要求为花朵涂色。 要求: 1)涂色的花朵区域必须是一个正方形矩阵,最小为一个22的正方形矩阵; 2)正方形矩阵中的花朵必须是同一种花朵; 3)只要正方形矩阵四个顶点不重合就算作不同的正方形矩阵(有部分区域重叠或者大正方形矩阵包含小正方形矩阵,按不同的正方形矩阵计算)。 已知方格纸的行数N(2≤N≤30)和列数M(2≤M≤30),及每个小正方形方格中花朵的种类,请帮助小明计算出,按要求有多少个正方形矩阵需要涂色。 例如:N=4,D = 5,矩阵如下图: https://img-blog.csdnimg.cn/direct/899e075d23174b00bf6e997ce43eec52.png 其中有3个正方形矩阵需要涂抹颜料(蓝色框区域和绿色区域的矩阵部分重叠按2个计算)。

输入

第一行输入两个正整数N(2≤N≤30)和M(2≤M≤30),N表示矩阵方格的行数,M表示矩阵方格的列数,两个正整数之间以一个空格隔开 第二行开始输入N行,每行M个字符(字符只包含a、b、c),字符之间以一个空格隔开

输出

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

样例

输入

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

输出

3

输入

9 11
b c b c a a a b b a b
c a c a b c a b a b a
a b b a b b b b c a b
b c c a b b b b a c c
a c b c b b b a a b a
c a c a b a b c b c a
c c b a c c a b c b c
c a c b a b a a c b c
a c b c a c b a b c b

输出

6

输入

5 8
b c b b a b a b
c a c c c a b c
b a c c c c a b
b c c c c a c c
a c b c a c b c

输出

5
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题