Área da maior ilha
A missão
Problema
Um mapa é um grid de 0s (água) e 1s (terra). Uma ilha é um grupo de células de terra conectadas para cima, para baixo, para a esquerda ou para a direita; vizinhos na diagonal não se conectam. A área de uma ilha é o seu número de células. Retorne a área da maior ilha, ou 0 se não houver terra.
Exemplos
Input: grid = [[1, 1, 0, 0], [1, 0, 0, 1], [0, 0, 1, 1], [0, 0, 1, 0]]
Output: 4
Por quê: a ilha do canto superior esquerdo tem 3 células e a da direita tem 4
Input: grid = [[1, 0, 1], [0, 1, 0], [1, 0, 1]]
Output: 1
Por quê: células na diagonal não se juntam, então há cinco ilhas de uma célula
Input: grid = [[0, 0], [0, 0]]
Output: 0
Por quê: edge case: nenhuma terra
Dicas
0 / 3
Isto é contagem de ilhas com uma mudança: em vez de contar quantas ilhas você começa, meça cada uma enquanto a explora.
Varra todas as células. Ao encontrar terra, explore a ilha inteira a partir dela com uma pilha ou uma fila e conte as células que você visitar.
Marque uma célula como visitada no momento em que a empilhar, por exemplo trocando-a por 0, para que ela nunca seja contada duas vezes nem inicie uma segunda busca. Guarde a maior contagem.
- Tempo-alvo
- O(rows · cols)
- Espaço-alvo
- O(rows · cols)
Restrições
- cells are 1 (land) or 0 (water)
Solução
Toda célula de terra pertence a exatamente uma ilha, e um flood fill a partir de qualquer uma das suas células visita a ilha inteira e nada mais. A varredura externa só inicia um preenchimento em terra ainda não visitada, e o preenchimento conta as células à medida que as desempilha. Afundar uma célula (trocá-la por 0) assim que ela é empilhada é a marca de visitada, então nenhuma célula é empilhada duas vezes. Uma pilha explícita evita que uma ilha grande atinja o limite de recursão do Python. Cada célula é varrida uma vez e empilhada no máximo uma vez, então o tempo é O(rows × cols); a pilha pode guardar O(rows × cols) células no pior caso. A função trabalha em uma cópia, para que o grid de quem chama fique intacto.
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]])) # -> 0Travou na ideia, e não no código? Number of Islands explica isso.