Área de la isla más grande
La misión
Problema
Un mapa es una cuadrícula de 0 (agua) y 1 (tierra). Una isla es un grupo de celdas de tierra conectadas hacia arriba, abajo, izquierda o derecha; los vecinos en diagonal no se conectan. El área de una isla es su cantidad de celdas. Devuelve el área de la isla más grande, o 0 si no hay tierra.
Ejemplos
Input: grid = [[1, 1, 0, 0], [1, 0, 0, 1], [0, 0, 1, 1], [0, 0, 1, 0]]
Output: 4
Por qué: la isla de arriba a la izquierda tiene 3 celdas y la de la derecha tiene 4
Input: grid = [[1, 0, 1], [0, 1, 0], [1, 0, 1]]
Output: 1
Por qué: las celdas en diagonal no se unen, así que hay cinco islas de una celda
Input: grid = [[0, 0], [0, 0]]
Output: 0
Por qué: caso límite: no hay nada de tierra
Pistas
0 / 3
Es el conteo de islas con un solo cambio: en lugar de contar cuántas islas empiezas, mide cada una mientras la exploras.
Recorre todas las celdas. Cuando encuentres tierra, explora desde ahí toda la isla con una pila o una cola y cuenta las celdas que visitas.
Marca una celda como visitada en el momento en que la apilas, por ejemplo poniéndola en 0, para que nunca se cuente dos veces ni inicie una segunda búsqueda. Quédate con el conteo más grande.
- Tiempo objetivo
- O(rows · cols)
- Espacio objetivo
- O(rows · cols)
Restricciones
- cells are 1 (land) or 0 (water)
Solución
Cada celda de tierra pertenece exactamente a una isla, y un flood fill (relleno por inundación) desde cualquiera de sus celdas visita toda la isla y nada más. El recorrido externo inicia un relleno solo en tierra que todavía no se visitó, y el relleno cuenta las celdas a medida que las saca. Hundir una celda (ponerla en 0) en cuanto se apila es la marca de visitado, así que ninguna celda se apila dos veces. Una pila (stack) explícita evita que una isla grande choque con el límite de recursión de Python. Cada celda se recorre una vez y se apila como máximo una vez, así que el tiempo es O(rows × cols); la pila puede contener O(rows × cols) celdas en el peor caso. La función trabaja sobre una copia, así que la cuadrícula de quien la llama queda intacta.
def largest_island(grid):
grid = [row[:] for row in grid] # sink cells in a copy
rows, cols = len(grid), len(grid[0])
best = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] != 1:
continue
grid[r][c] = 0
stack, area = [(r, c)], 0
while stack:
y, x = stack.pop()
area += 1
for ny, nx in ((y + 1, x), (y - 1, x), (y, x + 1), (y, x - 1)):
if 0 <= ny < rows and 0 <= nx < cols and grid[ny][nx] == 1:
grid[ny][nx] = 0 # visited the moment it is pushed
stack.append((ny, nx))
best = max(best, area)
return best
print(largest_island([[1, 1, 0, 0], [1, 0, 0, 1], [0, 0, 1, 1], [0, 0, 1, 0]])) # -> 4
print(largest_island([[1, 0, 1], [0, 1, 0], [1, 0, 1]])) # -> 1
print(largest_island([[0, 0], [0, 0]])) # -> 0¿Lo que te frena es la idea y no el código? Number of Islands lo explica.