Number of Islands

You are given a grid of size \( m \times n \) containing characters '1' (land) and '0' (water). An island is formed by connecting adjacent lands horizontally or vertically. Diagonal connections are not considered. Your task is to count the number of islands present in the grid.

Definition:

An island is a maximal group of connected cells such that each cell contains '1'. Two cells are connected if they are adjacent in one of the four directions: up, down, left, or right. Mathematically, if cell \((i,j)\) is '1', then any cell \((i+1,j)\), \((i-1,j)\), \((i,j+1)\), or \((i,j-1)\) with a value of '1' belongs to the same island.

It is guaranteed that all four edges of the grid are surrounded by water.

inputFormat

The input is given from standard input (stdin). The first line contains two integers ( m ) and ( n ), representing the number of rows and columns of the grid respectively. This is followed by ( m ) lines, each containing ( n ) space-separated characters (either '1' or '0') representing the grid.

outputFormat

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

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

1