#P3678. [CERC2016] 外观分析 Appearance Analysis

[CERC2016] 外观分析 Appearance Analysis

题目描述

你在萨格勒布拍摄了一张电气工程与计算机“C”楼的照片,它的尺寸相同的窗户整齐地排列在行列上。一些窗户上画着美妙的图案,你现在正在尝试分析有多少本质不同的创意画。

我们用一个r行c列的矩形格子图来描述一张照片。每个窗户都占据了一个矩形区域,并且所有窗户都有着相同的尺寸。一个窗户里的每个格子要么是空白的(用“.”表示),要么是被画过的(用“+”表示)。两个窗户的图案被认为是相同的,当且仅当其中有一个窗户旋转90度、180度、270度或360度后,放在另一个窗户上会完全匹配(包括边框)。当比较图案时,我们不允许翻转窗户。

所有窗户都规则地分布在行列中,窗户之间的边框用一格“#”字符表示。确切地说,在上下相邻的两个窗户之间,有恰好一行“#”字符,同时在第一行窗户之上或者最后一行窗户之下,也有恰好一行“#”字符。同理,在左右相邻的两个窗户之间,有恰好一列“#”字符,同时在第一列窗户之左或者最后一列窗户之右,也有恰好一列“#”字符。窗户的行数与列数是任意的,窗户的长宽也是任意的,不一定是正方形。但是,每个窗户至少占据一个格子,而且所有窗户的尺寸都是相同的。

请统计有多少本质不同的创意画。

输入格式

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

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

输出格式

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

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