#1779. [Cerc2016]Appearance Analysis

[Cerc2016]Appearance Analysis

Description

你在萨格勒布拍摄了一张电气工程与计算机“C”楼的照片,它的尺寸相同的窗户整齐地排列在行列上。一些窗户

上画着美妙的图案,你现在正在尝试分析有多少本质不同的创意画。我们用一个r行c列的矩形格子图来描述一张照

片。每个窗户都占据了一个矩形区域,并且所有窗户都有着相同的尺寸。一个窗户里的每个格子要么是空白的(用

“.”表示),要么是被画过的(用“+”表示)。两个窗户的图案被认为是相同的,当且仅当其中有一个窗户旋转

90度、180度、270度或360度后,放在另一个窗户上会完全匹配(包括边框)。当比较图案时,我们不允许翻转窗

户。所有窗户都规则地分布在行列中,窗户之间的边框用一格“#”字符表示。确切地说,在上下相邻的两个窗户

之间,有恰好一行“#”字符,同时在第一行窗户之上或者最后一行窗户之下,也有恰好一行“#”字符。同理,在

左右相邻的两个窗户之间,有恰好一列“#”字符,同时在第一列窗户之左或者最后一列窗户之右,也有恰好一列

“#”字符。窗户的行数与列数是任意的,窗户的长宽也是任意的,不一定是正方形。但是,每个窗户至少占据一

个格子,而且所有窗户的尺寸都是相同的。请统计有多少本质不同的创意画。

Format

Input

第一行包含两个正整数r,c(3<=r,c<=111),分别表示照片的行数和列数。

接下来r行,每行c个字符,分别表示照片的每一行。

Output

输出一行一个整数,即本质不同的创意画的数量。

Samples

11 16
################
#....#++++#+...#
#....#++.+#+...#
#....#.++.#++.+#
#....#....#++++#
################
#....#.+..#++++#
#..++#.+..#++.+#
#+...#....#.++.#
#+...#..++#....#
################
4