Island Counting

You are given a 2-dimensional grid of characters where each character is either '0' or '1'. A cell with '1' represents land and '0' represents water. An island is defined as a group of horizontally or vertically adjacent lands (i.e. connected 4-directionally). Diagonally adjacent cells are not considered connected.

Your task is to count the number of distinct islands in the grid.

Formally, if we denote the grid as \(G\) with \(m\) rows and \(n\) columns, two cells \(G[i][j]\) and \(G[k][l]\) belong to the same island if and only if there exists a sequence of cells \( (i_0,j_0), (i_1,j_1), \dots, (i_t,j_t) \) such that \( (i_0,j_0) = (i,j) \), \( (i_t,j_t) = (k,l) \), and for each \(0 \le r < t\), the cells \( (i_r,j_r) \) and \( (i_{r+1},j_{r+1}) \) are adjacent vertically or horizontally.

If the grid is empty (i.e. \(m=0\)), then the number of islands is defined to be 0.

inputFormat

The first line of input contains two integers \(m\) and \(n\) separated by a space, representing the number of rows and columns respectively. If \(m=0\), no additional lines follow.

The next \(m\) lines each contain a string of length \(n\) consisting only of the characters '0' and '1', representing a row of the grid.

outputFormat

Output a single integer representing the number of islands in the given grid on a single line.

0 0

0