Number of Islands
Recibes un mapa como una lista de cadenas de igual longitud, donde '1' es una casilla de tierra y '0' es una casilla de agua. Dos casillas de tierra pertenecen a la misma isla cuando comparten un lado: arriba, abajo, a la izquierda o a la derecha. Las casillas que solo se tocan por una esquina no están conectadas. Devuelve el número de islas.
Función
- gridstring-array
- el mapa, una cadena por fila
- Devuelveinteger
- el número de islas
Restricciones
1 ≤ grid.length ≤ 1501 ≤ grid[i].length ≤ 150- Todas las filas tienen la misma longitud.
- Cada carácter es
'0'o'1'.
Ejemplos
- Entrada
- grid = ["11000", "11000", "00100", "00011"]
- Salida
- 3
- Explicación
- Los cuatro cuadrados de la parte superior izquierda forman una isla. El cuadrado central de la tercera fila solo los toca por una esquina, así que es una segunda isla. El par de la parte inferior derecha es la tercera.
- Entrada
- grid = ["01110", "01000", "00011", "11001"]
- Salida
- 3
- Explicación
- Los tres cuadrados de la fila superior y el que está debajo de su extremo izquierdo forman una isla. El par de la derecha de la tercera fila se conecta con el cuadrado de la esquina inferior derecha, una segunda isla. El par inferior izquierdo es la tercera.
Para ir más allá
La tierra aparece ahora un cuadrado a la vez en un mapa de agua. ¿Puedes indicar el número de islas después de cada nuevo cuadrado sin volver a recorrer todo el mapa?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Recorre el mapa cuadrado por cuadrado. Cuando llegues a una casilla de tierra que ninguna isla anterior haya reclamado, ¿cuántas islas nuevas habrás encontrado?
Cuando encuentres una isla nueva, visita cada casilla de tierra conectada a ella y marca cada una como vista, para que el escaneo no vuelva a contar la misma isla.
Explora con una cola (en anchura) o una pila explícita (en profundidad) de casillas que aún quedan por visitar. Una búsqueda recursiva puede agotar la pila de llamadas en un mapa que sea una sola isla enorme, mientras que un bucle sobre tu propia cola o pila no puede.
Solución
Considera cada casilla de tierra como un nodo unido a las casillas de tierra contiguas: una isla es una pieza conectada. Recorre el mapa y, cada vez que llegues a tierra que no hayas visto, cuenta una nueva isla y aplícale un relleno por inundación, marcando todas sus casillas para que el recorrido no vuelva a contarlas.
Relleno por inundación con una pila explícita (DFS)
Intuición
Una casilla de tierra sin marcar no puede pertenecer a una isla que ya hayas contado, porque al contar una isla se marca por completo. Así que inicia una nueva isla. Una pila que gestionas tú marca el resto: cada casilla que extraes añade sus vecinas de tierra sin marcar, y cuando la pila está vacía, toda la isla está marcada.
Tu propia pila es importante porque un recorrido recursivo puede alcanzar una profundidad de 22,500 llamadas en un mapa de 150 × 150 compuesto completamente de tierra. Cada casilla se añade a la pila como máximo una vez y comprueba cuatro vecinas, así que el tiempo es O(rows × cols). Las marcas y la pila ocupan O(rows × cols) de espacio cuando el mapa es todo tierra.
Algoritmo
- Crea una marca de visitado para cada casilla y establece el recuento en 0.
- Recorre todas las casillas, omitiendo el agua y las casillas ya visitadas.
- En tierra sin visitar, suma 1 al recuento, marca la casilla y ponla en una pila.
- Mientras la pila no esté vacía, extrae una casilla y pon en la pila cada vecino dentro del mapa que sea tierra sin visitar, marcándolo antes de ponerlo.
- Devuelve el recuento cuando termine el recorrido.
def numIslands(grid):
rows, cols = len(grid), len(grid[0])
seen = [[False] * cols for _ in range(rows)]
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] != '1' or seen[r][c]:
continue
# Land that no island has claimed yet: a new island.
count += 1
seen[r][c] = True
stack = [(r, c)]
while stack:
i, j = stack.pop()
for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1' and not seen[ni][nj]:
# Mark on push, so no square enters the stack twice.
seen[ni][nj] = True
stack.append((ni, nj))
return countRelleno por inundación con una cola (BFS)
Intuición
El conteo funciona de la misma manera; solo cambia el orden de visita. Una cola toma las casillas del frente y añade los terrenos vecinos sin marcar al final, así que visita la isla en anillos: la primera casilla, después cada casilla a un paso de distancia y luego las que están a dos pasos. Cada casilla se visita una sola vez, en O(rows × cols) de tiempo y espacio.
El orden en anillos indica la distancia de cada casilla desde el inicio, así que el mismo bucle responde preguntas sobre el camino más corto en una cuadrícula con un número adicional por casilla.
Algoritmo
- Crea una marca de visitado para cada cuadrado y establece el contador en 0.
- Recorre todos los cuadrados, omitiendo el agua y los cuadrados ya visitados.
- En tierra no visitada, suma 1 al contador, marca el cuadrado y ponlo en una cola vacía.
- Mientras haya cuadrados en la cola, toma uno del principio y añade al final cada vecino dentro del mapa que sea tierra no visitada, marcándolo al añadirlo.
- Devuelve el contador cuando termine el recorrido.
def numIslands(grid):
rows, cols = len(grid), len(grid[0])
seen = [[False] * cols for _ in range(rows)]
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] != '1' or seen[r][c]:
continue
count += 1
seen[r][c] = True
stack = [(r, c)]
while stack:
i, j = stack.pop()
for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1' and not seen[ni][nj]:
seen[ni][nj] = True
stack.append((ni, nj))
return count
Errores comunes y casos límite
- Marcar una casilla al sacarla de la pila o la cola en lugar de cuando la metes. Después, la misma casilla se añade varias veces.
- Comparar una casilla con el número 1 en lugar del carácter
'1'. Cada fila es una cadena, así que cada casilla es un carácter. - Leer una casilla vecina antes de comprobar
0 ≤ row < rowsy0 ≤ col < cols. Después, una casilla de tierra en el borde lee fuera del mapa. - Escribir el recorrido recursivamente. Python se detiene por defecto tras 1,000 llamadas, y en otros lenguajes la pila puede desbordarse en una isla grande.
- Tomar el primer elemento de una lista de Python con
pop(0), lo que lleva un tiempo proporcional al tamaño de la lista. Usacollections.dequeypopleft().
Preguntas frecuentes4
¿Cuál es la complejidad temporal de Number of Islands?
O(rows × cols). El recorrido examina cada casilla una vez, y cada casilla de tierra se añade a la pila o cola una vez y comprueba cuatro vecinos. Las marcas de visitado y la pila o cola usan O(rows × cols) de espacio en un mapa que es todo tierra.
¿Deberías usar BFS o DFS para el número de islas?
Ambos son correctos en el mismo tiempo y espacio, porque el conteo solo necesita que se marque cada casilla de una isla. BFS con una cola nunca recurre; DFS es igual de seguro cuando usa una pila explícita.
¿Puedes resolver Número de islas con union-find?
Sí. Coloca cada casilla de tierra en su propio conjunto y comienza el recuento con el número de casillas de tierra. Une cada par de casillas de tierra vecinas y reduce el recuento en uno cada vez que una unión conecta dos conjuntos diferentes. Con compresión de caminos, el tiempo se acerca a O(rows × cols).
¿Puedes contar las islas sin un array independiente de elementos visitados?
Sí, si puedes cambiar el mapa: convierte cada casilla de tierra en agua en cuanto la alcances. Muchos lenguajes no pueden cambiar cadenas in situ, así que primero copias las filas en una cuadrícula de caracteres, lo que ocupa el mismo espacio que las marcas de visitado.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def numIslands(grid):
# Escribe el código aquíPrueba #1
Prueba #2
Argumento
grid = ["11000", "11000", "00100", "00011"]
Salida Esperada
3