Count Distinct Islands

You are given a grid with N rows and M columns consisting of the characters 0 and 1. Each cell with a value of 1 represents land, while 0 represents water. An island is defined as a group of horizontally or vertically connected lands.

Your task is to count the number of distinct islands in the grid. Formally, an island is a set of grid cells such that for any cell \((i,j)\) in the island, there exists a path connecting it to any other cell within the island via moves in the four cardinal directions (up, down, left, and right). In mathematical notation, two cells \((i_1,j_1)\) and \((i_2,j_2)\) are part of the same island if there is a sequence of cells \((i_1,j_1) = (p_0,q_0), (p_1,q_1), \ldots, (p_k,q_k) = (i_2,j_2)\) such that for every consecutive pair \((p_s,q_s)\) and \((p_{s+1},q_{s+1})\), we have \(|p_s-p_{s+1}|+|q_s-q_{s+1}| = 1\>.

Your solution must read input from stdin and produce the result to stdout.

inputFormat

The input is given via stdin as follows:

• The first line contains two space-separated integers, N and M, representing the number of rows and columns in the grid.
• This is followed by N lines, each containing a string of M characters (each character is either 0 or 1), representing a row of the grid.

outputFormat

Output a single integer to stdout that represents the number of distinct islands in the grid.

4 5
11000
11000
00100
00011

3