問題文
12 月已经开始,2014 年也即将迎来年末。因此,为了焕然一新,我决定更换壁纸图案来迎接 2015 年。
手边有纵向 R 行横 C 因为有一列布料,所以如果需要的话,我们决定从该布料中切出一部分用于壁纸设计。
从布料中切出设计时,必须沿着网格切割,并且设计必须是长方形的形状。
构成布料的每一个网格各自只是 1 被涂上了___种颜色。
其实我们每年都在追求有趣的设计,所以今年也决定制作一种作为有趣设计的“点对称设计”的纸样。
设计是“点对称设计”意味着,设计的大小纵向 H 行、横 W 当作为列时,
- H ≧ 2 和 W ≧ 2 很满意。 对于
- 对所有整数 i,j (1 ≦ i ≦ H, 1 ≦ j ≦ W) 来说,从上到下数第 i 第 j 格的颜色 c_{i,j} 等于从上到下数第 H-i+1 第 W-j+1 格的颜色 c_{H-i+1,W-j+1} 格的颜色。
指的是特定场合的事情。
根据生地的场所,也有各种有趣的点,即使纵横的大小和颜色的配置完全相同,切割出来的原始位置不同,也会形成不同的设计。而对于生地来说,所谓“点对称的设计”, 1 我想知道全部有多少种切割方法。
入力
输入是按以下格式从标准输入给出的。
R C s_1 s_2 : s_R
- 1 行上给出了生地的行数 R (1 ≦ R ≦ 250) 以及列数 C (1 ≦ C ≦ 250) 用空格分隔。
- 2 在 R 行中会提供与生地相关的信息。其中 i (1 ≦ i ≦ R) 行由长度组成 C 的字符串 s_i 。s_i 仅由半角小写英文字母构成,且从左边开始 j (1 ≦ j ≦ C) 第几个字符表示布料上从上数第 i 第 j 个格子的颜色。
- 对于不同的 2 个格子,如果表示上述颜色的字符相同,则表示用相同颜色涂色,如果不同,则表示用不同颜色涂色。
部分点
这个问题设置了部分得分。
- R ≦ 20 和 C ≦ 20 满足的数据集 1 全部答对的话,15 分将获得。
- R ≦ 100 和 C ≦ 100 满足的数据集 2 全部答对的话,在上述基础上还可 30 分将获得。
- 没有附加约束的数据集 如果您对 3 全部答对的话,在上述基础上 2 之上再额外 55 分可以获得,总共 100 分将获得。
出力
输出「中心对称设计」的设计数量, 1 每行一个输出。输出的末尾也要换行。
入力例1
2 10 codethanks documentsk
出力例1
2
布料如下所示。
| c | o | d | e | t | h | a | n | k | s |
| d | o | c | u | m | e | n | t | s | k |
例如,从上面 1 第 1 第几个格子作为左上角,从上面 2 第 3 第几个格子作为右下角,将竖 2 行横 3 列的区域切出来,
| c | o | d |
| d | o | c |
就可以得到「中心对称设计」。此外,还有,1 有可以切割的场所,所以答案是 2 。
入力例2
6 4 aaaa abba abba aaaa ccbb cdbb
出力例2
5
即使一个“点对称设计”包含另一个“点对称设计”,每个“点对称设计”都会被计算在内。
另外,在这个例子中, 它出现在
| b | b |
| b | b |
是 存在 2 部分中,2 也算作 1。