Distinct Islands Counting

You are given a grid of characters that represents a map, where each cell is either '1' (land) or '0' (water). An island is a group of connected lands (cells with '1') connected horizontally or vertically. Two islands are considered to be the same if and only if one island can be translated (moved without rotation) to equal the other. In other words, their shapes are identical. Mathematically, for two islands with coordinates ((i_1,j_1), (i_2,j_2), \ldots) and ((i'_1,j'_1), (i'_2,j'_2), \ldots), they are the same if there exists some (\Delta i) and (\Delta j) such that for every cell ((i,j)) in the first island, ((i+\Delta i, j+\Delta j)) is a cell in the second island.

Your task is to compute the number of distinct islands in the grid. Use any graph traversal algorithm such as DFS or BFS to explore the grid and determine the shape of each island relative to its starting point.

inputFormat

Input is read from standard input (stdin). The first line contains two integers (R) and (C), representing the number of rows and columns of the grid. This is followed by (R) lines, each containing (C) space-separated characters (each character is either '0' or '1').

outputFormat

Output a single integer (to standard output) which is the number of distinct islands.## sample

4 4
1 1 0 0
1 0 0 1
0 0 1 0
0 1 1 0

3