Distinct Islands

You are given a square grid of size \(n \times n\) where each cell is either \(0\) or \(1\). An island is formed by a group of adjacent cells with a value of \(1\), where adjacency is defined horizontally or vertically.

Two islands are considered identical if one can be translated, rotated (by \(90^\circ\), \(180^\circ\), or \(270^\circ\)) and/or reflected to obtain the other. In other words, regardless of where the island is located in the grid, its shape is defined by the relative positions of its cells. Formally, if the set of coordinates representing an island is \(S\), then after applying any of the eight possible transformations (including the identity transformation), the lexicographically smallest normalized shape is chosen as its canonical form. Your task is to compute how many distinct island shapes occur in the grid.

inputFormat

The input is read from standard input and has the following format:

The first line contains an integer \(n\) denoting the size of the grid (number of rows and columns).
Each of the next \(n\) lines contains \(n\) space-separated integers (either 0 or 1) representing the grid.

outputFormat

Output a single integer on standard output representing the number of distinct island shapes found in the grid.

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

3