P3678 [CERC2016] Appearance Analysis

You took a photo in Zagreb of the "C" building of Electrical Engineering and Computing, where same-sized windows are neatly arranged in rows and columns. Some windows contain beautiful designs, and you are trying to analyze how many essentially different creative drawings there are. We describe a photo using a rectangular grid with $r$ rows and $c$ columns. Each window occupies a rectangular region, and all windows have the same dimensions. In a window, each cell is either blank (denoted by ".") or painted (denoted by "+"). Two windows are considered to have the same design if and only if, after rotating one window by $90^\circ$, $180^\circ$, $270^\circ$, or $360^\circ$, it matches the other exactly (including borders). Flipping windows is not allowed when comparing designs. All windows are regularly placed in rows and columns, and the borders between windows are represented by the character "#". Specifically, between two vertically adjacent windows there is exactly one row of "#" characters, and there is also exactly one row of "#" characters above the first row of windows and below the last row of windows. Similarly, between two horizontally adjacent windows there is exactly one column of "#" characters, and there is also exactly one column of "#" characters to the left of the first column of windows and to the right of the last column of windows. The numbers of window rows and window columns are arbitrary, and the window width and height are arbitrary; windows are not necessarily square. However, each window occupies at least one cell, and all windows have the same size. Please count how many essentially different creative drawings there are.

The first line contains two positive integers $r, c$ ($3 \le r, c \le 111$), the numbers of rows and columns of the photo. Each of the next $r$ lines contains $c$ characters, describing the photo.

Output a single integer, the number of essentially different creative drawings.

Translated by ChatGPT 5