Counting Distinct Islands

Given a grid of size \(R \times C\) where each cell is either '1' (land) or '0' (water), count the number of distinct islands. An island is a group of connected '1's, where two cells are considered connected if they are adjacent horizontally or vertically.

You are to write a program that reads the grid from standard input and outputs the number of islands to standard output.

Note: If the grid is empty (i.e. \(R = 0\) or \(C = 0\)), the answer is 0.

inputFormat

The first line contains two integers \(R\) and \(C\), representing the number of rows and columns respectively. If \(R\) or \(C\) is 0, the grid is considered empty.

Then follow \(R\) lines, each containing \(C\) space-separated characters (each either '1' or '0') representing the grid.

outputFormat

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

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

3