Rotting Oranges

+10

Você recebe uma grade como uma lista de linhas de mesmo comprimento. Cada célula é 0 (vazia), 1 (uma laranja fresca) ou 2 (uma laranja podre). A cada minuto, cada laranja fresca que compartilha um lado com uma laranja podre, acima, abaixo, à esquerda ou à direita, apodrece. Retorne o número de minutos até que não reste nenhuma laranja fresca, ou -1 se alguma laranja fresca nunca puder apodrecer. Uma grade sem laranjas frescas no início precisa de 0 minutos.

Função

orangesRotting(grid: integer-2d-array) → integer

gridinteger-2d-array: a grade, uma lista de 0, 1 e 2 por linha
Retornainteger: os minutos até que nenhuma laranja esteja fresca, ou -1 se isso nunca acontecer

Restrições

1 ≤ grid.length ≤ 150
1 ≤ grid[i].length ≤ 150
Todas as linhas têm o mesmo comprimento.
Cada grid[i][j] é 0, 1 ou 2.

Exemplos

Entrada: grid = [[2, 1, 1, 0], [0, 1, 0, 1], [1, 1, 1, 1]]
Saída: 6
Explicação: Representando as células como (linha, coluna), a podridão começa em (0,0) e segue o único caminho: (0,1) no minuto 1, (0,2) e (1,1) no minuto 2, (2,1) no minuto 3, (2,0) e (2,2) no minuto 4, (2,3) no minuto 5. A laranja em (1,3) só toca (2,3), então é a última a apodrecer, no minuto 6.

+21 testes ocultos ao enviar

Para ir além

Suponha que cada laranja fresca precise de um número próprio de minutos para apodrecer depois que uma vizinha apodrece. Como você encontraria o tempo para que todas apodreçam, então?

Solução

O apodrecimento começa ao mesmo tempo em cada laranja podre e avança uma célula por minuto, então a resposta é uma distância: quantos passos a laranja fresca mais distante está da laranja podre mais próxima. A busca em largura mede exatamente isso, se você colocar todas as laranjas podres na fila antes de começar e percorrer a fila um nível por vez, um minuto de cada vez.

Simule minuto a minuto

Correta, mas não termina nos maiores testes

Intuição

Faça o que a história diz. A cada minuto, percorra toda a grade e liste cada laranja fresca que toque uma podre. Depois, apodreça todas elas, some um ao relógio e percorra a grade novamente. Pare quando uma varredura não encontrar nada para apodrecer. Se ainda houver uma laranja fresca na grade nesse momento, a podridão nunca conseguirá alcançá-la: retorne -1.

Liste primeiro, apodreça depois. Se você apodrecer uma laranja no meio de uma varredura, uma célula verificada mais tarde na mesma varredura a verá como podre e também apodrecerá; assim, a podridão se espalha por várias células em um minuto, e o relógio marcará um valor baixo demais.

Isso está correto, mas cada minuto custa uma varredura completa de rows × cols células, e o número de minutos pode chegar perto do número de células. Em uma grade de 150 × 150, na qual as laranjas frescas formam um único caminho sinuoso e a podridão está em uma de suas extremidades, a podridão precisa de 11,324 minutos: 11,324 varreduras de 22,500 células, cerca de 2.5 × 10^8 verificações de células, quase todas em células que não podem mudar.

Algoritmo

Defina os minutos como 0.
Percorra a grade e liste cada laranja fresca que tenha uma vizinha podre.
Se a lista estiver vazia, pare. Caso contrário, transforme em podres todas as laranjas listadas, some 1 aos minutos e percorra a grade novamente.
Retorne -1 se ainda restar uma laranja fresca; caso contrário, retorne os minutos.

def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    minutes = 0
    while True:
        # Find every fresh orange that touches a rotten one right now.
        to_rot = []
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] != 1:
                    continue
                for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 2:
                        to_rot.append((r, c))
                        break
        if not to_rot:
            break
        # Rot them only after the scan, so the rot moves one step a minute.
        for r, c in to_rot:
            grid[r][c] = 2
        minutes += 1
    for row in grid:
        if 1 in row:
            return -1
    return minutes

BFS com múltiplas fontes por níveis

Intuição

A varredura perde tempo com células distantes da ação. As únicas laranjas que podem apodrecer no minuto t+1 são as vizinhas frescas das laranjas que apodreceram no minuto t. Então, mantenha exatamente essas em uma fila: a fronteira do apodrecimento.

Comece a fila com todas as laranjas que estão podres no minuto 0, todas juntas. Essa é a parte de múltiplas fontes. Uma laranja fresca apodrece no minuto igual à sua distância até a laranja podre mais próxima, e uma busca em largura iniciada com todas as fontes alcança cada célula primeiro a partir da fonte mais próxima. Uma busca faz o trabalho de uma busca por fonte, além de encontrar o mínimo.

Em seguida, trabalhe por níveis. No início de um minuto, a fila contém k laranjas, aquelas que apodreceram no minuto anterior. Retire exatamente k do início; para cada uma, faça suas vizinhas frescas apodrecerem e adicione-as ao final. Quando as k terminarem, um minuto terá passado e a fila conterá a próxima fronteira. No primeiro exemplo, os níveis são {(0,0)}, {(0,1)}, {(0,2), (1,1)}, {(2,1)}, {(2,0), (2,2)}, {(2,3)}, {(1,3)}: seis etapas após o início, portanto, seis minutos.

Conte as laranjas frescas uma vez no início e diminua a contagem cada vez que uma apodrecer. Pare assim que ela chegar a 0; caso contrário, o último nível adicionaria um minuto em que nada apodrece, e retorne -1 se a fila ficar vazia enquanto a contagem estiver acima de 0. Cada célula entra na fila no máximo uma vez e verifica quatro vizinhas, então o trabalho é O(rows × cols).

Algoritmo

Coloque cada laranja podre em uma fila e conte as laranjas frescas.
Defina os minutos como 0. Enquanto a fila não estiver vazia e ainda houver laranjas frescas, some 1 aos minutos e anote o tamanho k da fila.
Retire k laranjas do início. Para cada vizinha fresca dentro da grade, marque-a como podre, diminua a contagem de laranjas frescas e adicione-a ao final.
Quando o loop terminar, retorne os minutos se a contagem de laranjas frescas for 0; caso contrário, retorne -1.

from collections import deque


def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    # Every orange that is rotten at minute 0 starts in the queue.
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while queue and fresh > 0:
        minutes += 1
        # The queue holds exactly the oranges that went rotten last minute.
        # Rot their fresh neighbours; those become the next minute's queue.
        for _ in range(len(queue)):
            r, c = queue.popleft()
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))
    return minutes if fresh == 0 else -1

Armadilhas e casos extremos

A maioria das respostas erradas aqui erra por um minuto ou começa a busca no lugar errado.

Contar um minuto para o último nível. Se o loop continuar até a fila ficar vazia, sua última iteração não apodrece nada e ainda assim adiciona 1. Pare assim que não houver mais nenhuma laranja fresca.
Começar a busca a partir de cada laranja podre, uma de cada vez. A primeira busca alcança todas as laranjas com seu próprio relógio, então duas fontes que deveriam se encontrar no meio dão um tempo alto demais: [[2, 1, 1, 1, 1, 1, 1, 2]] leva 3 minutos, não 6.
Apodrecer laranjas durante a varredura na versão minuto a minuto. Uma célula que aparece mais adiante na mesma varredura passa a vê-las como podres, e a podridão atravessa várias células em um minuto.
Retornar -1 porque não há nenhuma laranja podre. Se também não houver laranjas frescas, nada precisa acontecer: [[0]] retorna 0. A resposta só é -1 quando há laranjas frescas que nunca apodrecem.
Marcar uma laranja como podre quando você a retira da fila, em vez de quando a coloca nela. Assim, uma laranja ao lado de duas laranjas podres entra na fila duas vezes, e a contagem de laranjas frescas fica abaixo de zero.
Busca em profundidade. Ela segue um caminho até o fim, então a primeira vez que alcança uma laranja não diz nada sobre o minuto em que essa laranja apodrece.

Perguntas frequentes4

Qual é a complexidade de tempo de Rotting Oranges?

O(rows × cols) com busca em largura. A primeira varredura examina cada célula uma vez, e cada laranja entra na fila no máximo uma vez e verifica quatro vizinhas. A fila ocupa O(rows × cols) de espaço no pior caso: uma grade cheia de laranjas podres.

Por que usar BFS e não DFS para as Laranjas Podres?

A busca em largura visita as células na ordem de sua distância em relação ao início, e aqui a distância corresponde ao tempo: o nível k da busca é exatamente o conjunto de laranjas que apodrecem no minuto k. A busca em profundidade pode chegar a uma célula por um longo desvio antes de encontrar o caminho mais curto, então teria que revisitar as células sempre que encontrasse um caminho mais curto.

O que é BFS de múltiplas fontes?

Uma busca em largura que começa com várias células na fila à distância 0, em vez de uma só. Em uma única passagem, ela fornece a distância de cada célula até a fonte mais próxima, o mesmo resultado de uma busca por fonte, tomando-se o mínimo, pelo custo de uma busca. Qualquer questão sobre “distância até o X mais próximo” em uma grade usa esse método.

Você consegue resolver Rotting Oranges sem alterar a grade?

Sim. Mantenha um array separado de posições visitadas e verifique esse array em vez de escrever 2 na grade. Isso custa O(rows × cols) de memória extra, que a fila pode precisar de qualquer forma. Em linguagens que passam a grade por referência, escrever nela também altera a grade de quem chamou a função, algo sobre o qual um entrevistador pode perguntar.

Python

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

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

grid = [[2, 1, 1, 0], [0, 1, 0, 1], [1, 1, 1, 1]]

Esperado