Number of Islands

Un mapa llega como una lista de filas de igual longitud. Cada carácter es 1, un cuadrado de tierra, o 0, un cuadrado de agua. Dos cuadrados de tierra pertenecen a la misma isla cuando uno está directamente encima, debajo, a la izquierda o a la derecha del otro. Los cuadrados que solo se tocan en una esquina no están conectados.

Considera el mapa ["11000", "11000", "00100", "00011"]:

• los cuatro cuadrados de tierra de la esquina superior izquierda forman una isla,
• el cuadrado único de la fila del medio es una segunda isla, ya que solo toca la primera en una esquina,
• los dos cuadrados de la esquina inferior derecha forman una tercera.

Así que el mapa contiene 3 islas.

El mapa es en realidad un grafo: cada cuadrado de tierra es un nodo, y una arista une dos cuadrados de tierra que comparten un lado. Contar las islas significa contar las componentes conexas de ese grafo. Cada vez que encuentras un cuadrado de tierra que aún no has visitado, has encontrado una nueva isla y exploras toda ella antes de continuar.

Escribe una función llamada numIslands que reciba grid, una lista de cadenas formadas por 1 (tierra) y 0 (agua), y devuelva el número de islas. Una isla es un grupo de casillas de tierra conectadas hacia arriba, abajo, la izquierda o la derecha.

Por ejemplo, ["01110", "01000", "00011", "11001"] devuelve 3: la forma de las filas superiores, el grupo de la derecha y el par de la esquina inferior izquierda.

Restricciones: 1 <= número de filas, número de columnas <= 150. Todas las filas tienen la misma longitud.