Un mapa de \(m \times n\) tiene tierra (1) y agua (0). Una isla es un grupo de celdas de tierra conectadas horizontal o verticalmente (no en diagonal). Todo lo que está fuera del mapa es agua. Cuenta las islas.

Entrada

La primera línea tiene \(m\) y \(n\) \((1 \le m, n \le 300)\) y siguen \(m\) líneas con \(n\) caracteres 0 o 1 cada una, sin espacios.

Salida

La cantidad de islas.

Nota

Una isla puede tener \(9 \cdot 10^4\) celdas: cuidado con la profundidad de la recursión.

Ejemplo 1

Entrada

4 5
11110
11010
11000
00000

Salida

1

Ejemplo 2

Entrada

4 5
11000
11000
00100
00011

Salida

3

Basado en el problema 200 de LeetCode, Number of Islands, adaptado a entrada y salida estándar; enunciado redactado para este juez. Es parte de la lista Grind 75 de Yangshun Tay.