Number of Islands

Q: Qual é a complexidade de tempo de Number of Islands?

O(rows × cols). A varredura verifica cada quadrado uma vez, e cada quadrado de terra entra na pilha ou na fila uma vez e verifica quatro vizinhos. As marcações de visitados e a pilha ou fila usam O(rows × cols) de espaço em um mapa totalmente coberto por terra.

Q: Você deve usar BFS ou DFS para o problema Number of Islands?

Ambos estão corretos em relação ao tempo e ao espaço, porque a contagem só precisa que cada quadrado de uma ilha seja marcado. BFS com uma fila nunca usa recursão; DFS é igualmente seguro quando usa uma pilha explícita.

Q: Você consegue resolver Número de Ilhas com union-find?

Sim. Coloque cada quadrado de terra em seu próprio conjunto e comece a contagem com o número de quadrados de terra. Una cada par de quadrados de terra vizinhos e diminua a contagem em um sempre que uma união conectar dois conjuntos diferentes. Com compressão de caminho, o tempo fica próximo de O(rows × cols).

Q: Você consegue contar ilhas sem um array separado para os elementos visitados?

Sim, se você puder alterar o mapa: transforme cada quadrado de terra em água assim que chegar até ele. Muitas linguagens não podem alterar strings diretamente, então primeiro você copia as linhas para uma grade de caracteres, o que ocupa o mesmo espaço que as marcações de áreas visitadas.

MédioGrafos

+10

Você recebe um mapa como uma lista de strings de mesmo comprimento, em que '1' é um quadrado de terra e '0' é um quadrado de água. Dois quadrados de terra pertencem à mesma ilha quando compartilham um lado: acima, abaixo, à esquerda ou à direita. Quadrados que se encontram apenas em um canto não estão conectados. Retorne o número de ilhas.

Função

numIslands(grid: string-array) → integer

gridstring-array: o mapa, uma string por linha
Retornainteger: o número de ilhas

Restrições

1 ≤ grid.length ≤ 150
1 ≤ grid[i].length ≤ 150
Cada linha tem o mesmo comprimento.
Todo caractere é '0' ou '1'.

Exemplos

Entrada: grid = ["11000", "11000", "00100", "00011"]
Saída: 3
Explicação: Os quatro quadrados no canto superior esquerdo formam uma ilha. O quadrado do meio da terceira linha só toca neles por um canto, então é uma segunda ilha. O par no canto inferior direito é a terceira.

Para ir além

A terra agora aparece um quadrado por vez em um mapa de água. Você consegue informar o número de ilhas após cada novo quadrado sem examinar o mapa inteiro novamente?

Solução

Trate cada quadrado de terra como um nó conectado aos quadrados de terra ao lado: uma ilha é uma parte conectada. Percorra o mapa e, sempre que chegar a uma área de terra que ainda não viu, conte uma nova ilha e preencha-a por inundação, marcando todos os seus quadrados para que a varredura não a conte novamente.

Preenchimento por inundação com uma pilha explícita (DFS)

Intuição

Um quadrado de terra não marcado não pode pertencer a uma ilha que você já contou, porque contar uma ilha marca todos os seus quadrados. Portanto, ele inicia uma nova ilha. Uma pilha que você gerencia por conta própria marca o restante: cada quadrado que você retira da pilha adiciona à pilha seus vizinhos de terra não marcados e, quando a pilha fica vazia, toda a ilha está marcada.

Sua própria pilha é importante porque um preenchimento recursivo pode chegar a 22,500 chamadas de profundidade em um mapa de 150 × 150 de terra sólida. Cada quadrado é adicionado à pilha no máximo uma vez e verifica quatro vizinhos, então o tempo é O(rows × cols). As marcações e a pilha ocupam O(rows × cols) de espaço quando o mapa é todo de terra.

Algoritmo

Crie uma marcação de visitado para cada quadrado e defina a contagem como 0.
Percorra todos os quadrados, ignorando a água e os quadrados já visitados.
Em terra não visitada, adicione 1 à contagem, marque o quadrado e coloque-o em uma pilha.
Enquanto a pilha não estiver vazia, retire um quadrado e coloque na pilha cada vizinho dentro do mapa que seja terra não visitada, marcando-o antes de colocá-lo.
Retorne a contagem quando a varredura terminar.

def numIslands(grid):
    rows, cols = len(grid), len(grid[0])
    seen = [[False] * cols for _ in range(rows)]
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != '1' or seen[r][c]:
                continue
            # Land that no island has claimed yet: a new island.
            count += 1
            seen[r][c] = True
            stack = [(r, c)]
            while stack:
                i, j = stack.pop()
                for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
                    if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1' and not seen[ni][nj]:
                        # Mark on push, so no square enters the stack twice.
                        seen[ni][nj] = True
                        stack.append((ni, nj))
    return count

Preenchimento por inundação com uma fila (BFS)

Intuição

A contagem funciona da mesma forma; apenas a ordem de visita muda. Uma fila retira quadrados do início e adiciona vizinhos de terra não marcados ao final, então percorre a ilha em anéis: o primeiro quadrado, depois todos os quadrados a uma etapa de distância, depois os que estão a duas etapas. Cada quadrado ainda é visitado uma vez, em tempo e espaço O(rows × cols).

A ordem em anéis fornece a distância de cada quadrado até o início, então o mesmo loop responde a perguntas sobre o caminho mais curto em uma grade com um número extra por quadrado.

Algoritmo

Crie uma marca de visitado para cada quadrado e defina a contagem como 0.
Percorra cada quadrado, ignorando a água e os quadrados já visitados.
Em terra não visitada, adicione 1 à contagem, marque o quadrado e coloque-o em uma fila vazia.
Enquanto houver quadrados na fila, retire um do início e adicione ao final cada vizinho dentro do mapa que seja terra não visitada, marcando-o ao adicioná-lo.
Retorne a contagem quando a varredura terminar.

def numIslands(grid):
    rows, cols = len(grid), len(grid[0])
    seen = [[False] * cols for _ in range(rows)]
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != '1' or seen[r][c]:
                continue
            count += 1
            seen[r][c] = True
            stack = [(r, c)]
            while stack:
                i, j = stack.pop()
                for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
                    if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1' and not seen[ni][nj]:
                        seen[ni][nj] = True
                        stack.append((ni, nj))
    return count

Armadilhas e casos extremos

Marcar uma célula quando você a retira da pilha ou da fila, em vez de quando a coloca nela. Assim, a mesma célula entra várias vezes.
Comparar uma célula com o número 1 em vez do caractere '1'. Cada linha é uma string, então cada célula é um caractere.
Ler uma célula vizinha antes de verificar 0 ≤ row < rows e 0 ≤ col < cols. Assim, uma célula de terra na borda tenta ler fora do mapa.
Fazer o preenchimento recursivamente. Por padrão, Python para após 1.000 chamadas, e outras linguagens podem estourar a pilha em uma ilha grande.
Remover o primeiro elemento de uma lista em Python com pop(0), o que leva um tempo proporcional ao tamanho da lista. Use collections.deque e popleft().

Perguntas frequentes4

Qual é a complexidade de tempo de Number of Islands?

O(rows × cols). A varredura verifica cada quadrado uma vez, e cada quadrado de terra entra na pilha ou na fila uma vez e verifica quatro vizinhos. As marcações de visitados e a pilha ou fila usam O(rows × cols) de espaço em um mapa totalmente coberto por terra.

Você deve usar BFS ou DFS para o problema Number of Islands?

Ambos estão corretos em relação ao tempo e ao espaço, porque a contagem só precisa que cada quadrado de uma ilha seja marcado. BFS com uma fila nunca usa recursão; DFS é igualmente seguro quando usa uma pilha explícita.

Você consegue resolver Número de Ilhas com union-find?

Sim. Coloque cada quadrado de terra em seu próprio conjunto e comece a contagem com o número de quadrados de terra. Una cada par de quadrados de terra vizinhos e diminua a contagem em um sempre que uma união conectar dois conjuntos diferentes. Com compressão de caminho, o tempo fica próximo de O(rows × cols).

Você consegue contar ilhas sem um array separado para os elementos visitados?

Sim, se você puder alterar o mapa: transforme cada quadrado de terra em água assim que chegar até ele. Muitas linguagens não podem alterar strings diretamente, então primeiro você copia as linhas para uma grade de caracteres, o que ocupa o mesmo espaço que as marcações de áreas visitadas.

def numIslands(grid):
    # Escreva o código aqui

Teste #1

Teste #2

Argumento

grid = ["11000", "11000", "00100", "00011"]

Saída Esperada