Count Distinct Islands

You are given an \( m \times n \) grid consisting of characters '1' (land) and '0' (water). An island is a group of adjacent lands connected horizontally or vertically. Two cells belong to the same island if they are connected directly via horizontal or vertical moves.

Your task is to count the number of distinct islands in the grid.

Note: You must use depth-first search (DFS) or a similar traversal strategy to explore the grid, marking cells as visited to avoid counting the same island more than once.

Input is provided via standard input (stdin) and output should be printed to standard output (stdout).

inputFormat

The first line contains two integers \( m \) and \( n \), representing the number of rows and columns in the grid respectively. The following \( m \) lines each contain \( n \) space-separated characters (either '0' or '1'), representing the grid.

outputFormat

Output a single integer which is the number of distinct islands found in the grid.

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

3