Perímetro de uma ilha
A missão
Problema
Um grid guarda 1 para terra e 0 para água, e toda a terra forma uma única ilha conectada, sem lagos dentro dela. Meça o comprimento do litoral da ilha, contando uma unidade para cada borda de célula que encosta na água ou no limite do grid.
Exemplos
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ê: um quadrado sólido de quatro células tem oito lados expostos
Input: grid = [[1]]
Output: 4
Por quê: edge case: uma célula isolada fica exposta em todos os lados
Dicas
0 / 3
Você não precisa percorrer o litoral em ordem. Cada unidade de litoral pertence a exatamente uma célula de terra, então as células podem ser visitadas em qualquer ordem.
Olhe para uma única célula de terra e pergunte quais dos seus quatro lados estão voltados para algo que não é terra.
Varra o grid inteiro. Para cada célula de terra, verifique as quatro posições vizinhas e some um para cada vizinho que esteja fora do grid ou seja água. O total acumulado é o perímetro.
- Tempo-alvo
- O(rows · cols)
- Espaço-alvo
- O(1)
Restrições
- cells are 1 (land) or 0 (water)
- the land forms one connected island with no lakes
Solução
Cada unidade de litoral é um lado de uma célula de terra, então o perímetro pode ser somado célula por célula, em vez de ser traçado como um contorno. Um lado conta quando o vizinho naquela direção é água, ou quando ele cai totalmente fora do grid, que é a mesma verificação com o teste de limites embutido. Isso transforma tudo em uma varredura simples, com quatro sondagens por célula e nenhum estado de percurso (traversal). O tempo é O(rows * cols) e o espaço é 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]])) # -> 4Travou na ideia, e não no código? Percurso em grid explica isso.