Number of Islands

You are given a grid of cells where each cell is either land ('1') or water ('0'). An island is defined as a group of horizontally or vertically connected lands. Your task is to write a program to count the number of islands in the grid.

The problem can be mathematically described as follows. Consider a grid \(G\) of dimensions \(m \times n\). Two cells \((i,j)\) and \((k,l)\) belong to the same island if and only if they are connected through adjacent (up, down, left, right) land cells. Formally, if we define an adjacency relation \(R\) such that:

[ (i,j) R (k,l) \quad \text{if} \quad |i-k| + |j-l| = 1 \text{ and } G[i][j] = G[k][l] = '1', ]

then the number of islands is the number of connected components under the relation \(R\). If the grid is empty, consider the number of islands to be 0.

inputFormat

The input is given via standard input (stdin) and has the following format:

• The first line contains a single integer \(m\) which represents the number of rows in the grid. If \(m = 0\), the grid is empty.
• If \(m > 0\), then the next \(m\) lines each contain space-separated characters ('0' or '1') representing the cells in that row.

Note: All rows will have the same number of columns.

outputFormat

Output a single integer to standard output (stdout) — the number of islands in the grid.

## sample

0

0

</p>