Perímetro de una isla
La misión
Problema
Una cuadrícula guarda 1 para la tierra y 0 para el agua, y toda la tierra forma una sola isla conexa, sin lagos en su interior. Mide la longitud de la costa de la isla: cuenta una unidad por cada borde de celda que dé al agua o al límite de la cuadrícula.
Ejemplos
Input: grid = [[0, 1, 0, 0],
[1, 1, 1, 0],
[0, 1, 0, 0],
[1, 1, 0, 0]]
Output: 16
Input: grid = [[1, 1],
[1, 1]]
Output: 8
Por qué: un cuadrado macizo de cuatro celdas tiene ocho lados expuestos
Input: grid = [[1]]
Output: 4
Por qué: caso límite: una celda sola queda expuesta por todos sus lados
Pistas
0 / 3
No tienes que recorrer la costa en orden. Cada unidad de costa pertenece exactamente a una celda de tierra, así que puedes visitar las celdas en el orden que quieras.
Mira una sola celda de tierra y pregúntate cuáles de sus cuatro lados dan a algo que no es tierra.
Recorre toda la cuadrícula. Para cada celda de tierra, revisa las cuatro posiciones vecinas y suma uno por cada vecino que esté fuera de la cuadrícula o sea agua. El total acumulado es el perímetro.
- Tiempo objetivo
- O(rows · cols)
- Espacio objetivo
- O(1)
Restricciones
- cells are 1 (land) or 0 (water)
- the land forms one connected island with no lakes
Solución
Cada unidad de costa es un lado de una celda de tierra, así que el perímetro se puede sumar celda por celda en lugar de trazarlo como un contorno cerrado. Un lado cuenta cuando el vecino en esa dirección es agua o cuando cae por completo fuera de la cuadrícula, que es la misma comprobación con el control de límites incluido. Así, todo se reduce a un recorrido simple, con cuatro comprobaciones por celda y sin estado que mantener. El tiempo es O(rows * cols) y el espacio es O(1).
def perimeter(g):
rows, cols, total = len(g), len(g[0]), 0
for r in range(rows):
for c in range(cols):
if g[r][c] != 1:
continue
for nr, nc in ((r-1, c), (r+1, c), (r, c-1), (r, c+1)):
off = not (0 <= nr < rows and 0 <= nc < cols)
if off or g[nr][nc] == 0: # that side faces water or the edge
total += 1
return total
print(perimeter([[0, 1, 0, 0], [1, 1, 1, 0], [0, 1, 0, 0], [1, 1, 0, 0]])) # -> 16
print(perimeter([[1, 1], [1, 1]])) # -> 8
print(perimeter([[1]])) # -> 4¿Lo que te frena es la idea y no el código? Recorrido de cuadrículas lo explica.