← 返回题目列表

AtCoder · code_thanks_festival_14_quala_h

H. 改造

中文机器翻译题面 查看原题

問題文

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。