eolymp
bolt
Try our new interface for solving problems
Problems

Kinds of figures

Kinds of figures

Consider a rectangular table with \textbf{N} rows, \textbf{M} columns. Each cell of the table is either \textit{free} (marked as '\textbf{.}') or filled (marked as '\textbf{*}'). Neighboring filled cells form \textit{figures}. More formally: \begin{itemize} \item cells are considered \textit{neighboring} if and only if they have common edge; \item filled cells belong to the same figure if and only if there is a sequence of filled cells which starts at oneof the given cells and finishes at another given, and each next cell is a neighbor of the previous. \end{itemize} Figures \textbf{A} and \textbf{B} are called \textit{figures of the same kind}, if and only if one of them can be obtained from another by shifting (without rotation). Your task is to write a program, which determines the total number of figures and number of different kinds of figures. \InputFile Your program should read numbers of rows \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{1234}), number of columns \textbf{M} (\textbf{1} ≤ \textbf{M} ≤ \textbf{1234}), and \textbf{N} lines consisting of exactly \textbf{M} characters '\textbf{*}' and/or '\textbf{.}' each. \OutputFile Your program should write two space-separated integers in one row --- the total number of figures and number of different kinds of figures.
Time limit 1 second
Memory limit 256 MiB
Input example #1
7 8
****.**.
****.**.
.....**.
.*.*.**.
.*.*...*
*.*.****
*.*.*.*.
Output example #1
7 4
Source ACM-ICPC Ukraine 2012, 2nd Stage Ukraine, September 6, 2012