Counting Distinct Islands

You are given a matrix of size n × m consisting of 0s and 1s. A cell with a value of 1 represents land and 0 represents water. An island is defined as a group of adjacent lands connected horizontally or vertically. Two cells are connected if they share a common side. The aim is to count the number of distinct islands in the grid.

An island can be formally characterized by the property that if a cell with coordinates \( (i, j) \) is part of an island, then any cell with value 1 and located at \( (i \pm 1, j) \) or \( (i, j \pm 1) \) is also part of the same island.

Note: Boundary cells that are 1 are also considered as regular parts of an island.

inputFormat

The first line of input contains two integers, n and m, representing the number of rows and columns respectively. This is followed by n lines, each containing m space-separated integers (each either 0 or 1), representing the matrix.

outputFormat

Output a single integer representing the number of distinct islands in the matrix.

4 5
1 1 0 0 0
1 1 0 1 0
0 0 0 1 1
0 1 0 0 0

3