Distinct Tetris Pieces

Given an \(n \times m\) grid where each cell is colored, a Tetris piece is defined as a connected component of cells of the same color. Two cells are directly connected if they share an edge (up, down, left, or right) and have the same color. Two cells are indirectly connected if there is a path of directly connected same-colored cells between them.

A Tetris piece consists of one cell and all cells directly or indirectly connected to it. Two Tetris pieces are considered to be of the same type if and only if one can be translated (i.e., shifted in the grid without rotation or reflection) to completely coincide with the other. Note that even if two pieces have different colors, they are considered the same type provided their shapes (relative positions of the cells) are identical.

Your task is to determine the number of distinct types of Tetris pieces present in the grid.

In summary:

• Input a grid of size \(n \times m\).
• Identify each connected component (Tetris piece) based on 4-directional connectivity (up, down, left, right) among cells with the same color.
• Normalize the shape of each piece by translating it so that its top-left cell is at \((0,0)\).
• Count the number of distinct shapes.

inputFormat

The first line contains two space-separated integers \(n\) and \(m\) indicating the number of rows and columns.

Each of the following \(n\) lines contains a string of length \(m\) representing the colors of the grid cells. Characters in the string denote the color of each cell.

outputFormat

Output a single integer: the number of distinct Tetris piece types in the grid.

sample

3 3
AAA
AAA
AAA

1