Count Islands

Given a grid representing a map where \(1\) indicates land and \(0\) indicates water, count the number of islands. An island is defined as a group of connected ones (\(1\)) that are adjacent horizontally or vertically (diagonals do not count). You may assume that all four edges of the grid are surrounded by water.

This problem requires you to perform a search (such as DFS or BFS) on the grid. Efficient handling of recursion and proper marking of visited cells is key to solving this problem.

inputFormat

The input is read from standard input (stdin). The first line contains a single integer (m), representing the number of rows in the grid. Each of the next (m) lines contains a string of equal length, composed solely of the characters '1' and '0'. It is guaranteed that all rows are of equal length.

outputFormat

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

4
11110
11010
11000
00000

1