MAKING A LARGE ISLAND HARD
problema
Você recebe uma grade n × n de 0 (água) e 1 (terra). Uma ilha é um grupo de
terras ligadas na horizontal ou na vertical. Você pode transformar no máximo um 0 em
1. Retorne a área da maior ilha possível depois dessa troca.
Testar cada 0 e recontar as ilhas do zero custaria O(n⁴). O truque é medir cada ilha uma vez só: primeiro rotula cada ilha com um id e guarda a área dela, depois cada 0 só precisa olhar os 4 vizinhos.
Exemplo 1 ·
[[1,1,0],[1,0,1],[0,0,1]] → 6
Virar o 0 do centro (ou o do canto de cima) junta a ilha de 3 com a de 2: 3 + 2 + 1 = 6.
Exemplo 2 ·
[[1,1],[1,1]] → 4
Não há 0 para virar: a resposta é a própria ilha, n² = 4.
Exemplo 3 ·
[[0,0],[0,0]] → 1
Só água: virar qualquer 0 cria uma ilha de área 1.
Restrições: 1 ≤ n ≤ 500 · cada célula é 0 ou 1