Count Islands in a Grid

You are given a grid representing a map where each cell is either land or water. The grid is represented by a matrix \(A\) of size \(m \times n\) where each element \(A_{ij}\) is either 1 (land) or 0 (water). Two land cells are considered connected if they are adjacent vertically or horizontally (i.e., up, down, left, or right). An island is defined as a maximal set of connected 1's. Your task is to count the number of islands in the grid.

Note: Cells are only connected in the four cardinal directions. Diagonal connections do not count.

For example, given the grid:

1 1 0 0 0
1 1 0 1 1
0 0 0 1 1
0 0 0 0 0
1 1 0 0 0

There are 3 islands.

The connectivity can be formally defined as: $$ \text{neighbors}(i,j) = \{(i-1,j), (i+1,j), (i,j-1), (i,j+1)\}. $$

inputFormat

The input is read from standard input (stdin) and is formatted as follows:

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

You can assume that \(1 \leq m, n \leq 1000\) and each cell is either 0 or 1.

outputFormat

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

## sample

5 5
1 1 0 0 0
1 1 0 1 1
0 0 0 1 1
0 0 0 0 0
1 1 0 0 0

3