Maurício Antunes

Posted on Jul 18 • Edited on Jul 22

Resolvendo o "Rotting Oranges"

#dsa #bfs #leetcode

Hoje a leitura é sobre como resolver o leetcode Rotting Oranges

Vamos passar por como resolver o problema, como entender algumas palavras-chave da descrição e o código da solução em Python.

O problema

Em uma matriz m x n, cada uma das posição pode ter três valores:

0 - uma posição vazia;
1 - uma laranja fresquinha;
2 - uma laranja podre.

A cada minuto, uma laranja fresca que está perto de uma podre vai apodrecer também.

Precisamos retornar o número de minutos passados até que todas laranjas estejam podres, ou -1 caso não seja possível ter todas elas apodrecidas.

Pensando no problema

Pra ajudar na resolução do problema, é fundamental que a gente consiga visualizar a disposição dessa matriz com algumas laranjas posicionadas:

Com essa disposição, quantos minutos demoraria para todas ficarem podres?

A) 5
B) 3
C) 4

Talvez eu tenha decepcionado você, mas a resposta não é 4 nem 5.
Algumas pessoas pensam que é 4 porque parece ser o maior caminho, se partir da laranja podre que fica embaixo. Outras pessoas pensam que é 5 porque é o número total de laranjas frescas.

Demoram 3 minutos pra que todas as laranjas fiquem podres.

O racional por trás é que a cada minuto mais de uma laranja pode ficar podre. Ou seja, as laranjas vão ficando podre simultaneamente. Guarde bem essa palavra.

Essa matriz é um grafo. Sim, matrizes são grafos. É possível codificar em uma matriz um grafo.

E no que saber isso muda? Primeiramente, isso facilita nossa compreensão sobre o problema. Nosso objetivo é dizer quanto tempo demora até todas laranjas ficarem podres, tentando conectar os pontos (laranjas podres e laranjas frescas). Problemas onde temos conexões entre pontos em uma matriz têm cheiro de grafo.

Há duas maneiras bem famosas de resolver problemas com grafos: DFS (Depth-First Search) e BFS (Breadth-First Search).

Pra esse problema, vamos usar BFS. A motivação tem a ver com a palavra simultaneamente. Quando usamos DFS pra resolver um problema, usamos stack. E uma stack é uma estrutura de dados usada em recursão. Quando usamos recursão, nós esgotamos a possibilidade de um caminho antes de testar outras opções, o que impede que seja simultâneo.

Diferente da stack, uma deque vai nos ajudar a procurar as laranjas simultaneamente.

Nesse problema, por exemplo, usar recursão contaria o caminho partindo de uma única laranja podre, contando de forma errônea.

Passos do algoritmo

Contar quantas laranjas frescas temos. Enquanto elas forem apodrecendo, quando chegar a ZERO, podemos usar isso como condição de parada.
Coletar as posições das laranjas podres. A razão é que, sabendo onde elas estão, podemos usar BFS para iterar em todas as laranjas podres simultaneamente.
Caminhar em todas direções, exceto nas diagonais, tentando achar novas laranjas para apodrecer.

Código da solução

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        minutes = 0

        queue = deque()
        fresh = 0

        for row in range(len(grid)):
            for col in range(len(grid[0])):
                if grid[row][col] == 2:
                    queue.append((row, col))
                elif grid[row][col] == 1:
                    fresh += 1

        deltas = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        while queue and fresh:
            length = len(queue)

            for _ in range(length):
                row, col = queue.popleft()

                for dr, dc in deltas:
                    next_row, next_col = row + dr, col + dc

                    if (
                        next_row in range(len(grid))
                        and next_col in range(len(grid[0]))
                        and grid[next_row][next_col] == 1
                    ):
                        grid[next_row][next_col] = 2
                        queue.append((next_row, next_col))
                        fresh -= 1
            minutes += 1

        return minutes if fresh == 0 else -1

Apesar do código ser um pouco longo (resolução de problemas de grafo costumam ter bastante código), ele não é tão complexo. Pelo menos não dá aquela sensação de ter que tirar um coelho da cachola por linha.

Começamos com algumas variáveis importantes:

Uma deque pra BFS;
minutes pra guardar o resultado final;
E fresh pra contar quantas laranjas frescas temos.

Agora contamos quantas laranjas frescas temos e quais são as laranjas podres:

for row in range(len(grid)):
    for col in range(len(grid[0])):
        if grid[row][col] == 2:
            queue.append((row, col))
        elif grid[row][col] == 1:
            fresh += 1

Agora vem um bloco ligeiramente complexo:

deltas = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while queue and fresh:
    length = len(queue)

    for _ in range(length):
        row, col = queue.popleft()

        for dr, dc in deltas:
            next_row, next_col = row + dr, col + dc

            if (
                next_row in range(len(grid))
                and next_col in range(len(grid[0]))
                and grid[next_row][next_col] == 1
            ):
                grid[next_row][next_col] = 2
                queue.append((next_row, next_col))
                fresh -= 1
    minutes += 1

deltas é uma variável pra guardar todas as direções nas quais podemos caminhar. Em uma matriz m x n podemos caminhar uma coluna a esquerda, uma linha abaixo, etc.

while queue and fresh garante nossa condição de parada. Enquanto a gente tiver laranjas pra adicionar e ainda ter laranjas frescas, precisamos continuar procurando laranjas podres para que elas apodreçam todas as outras que estão ao alcance.

Agora vem a parte mais tricky: o for dentro do while.
Ele é essencial para que a gente conte os minutos das laranjas podres simultaneamente.

Você pode fazer o teste aí. Abra um interpretador do Python, importe o deque, crie uma deque e comece a remover os elementos da esquerda e adicionando à direita.

O for garante que a gente itere, por exemplo, na primeira vez, todas as laranjas podres e continue a seguir a mesma estratégia pras próximas. Se no próximo loop a gente enfileirar mais 3 laranjas podres, vamos iterar nessas 3 laranjas que vão adicionar mais n laranjas, e assim por diante.

Agora mais um for. Esse iterando em todas as direções:

for dr, dc in deltas:
    next_row, next_col = row + dr, col + dc

    if (
        next_row in range(len(grid))
        and next_col in range(len(grid[0]))
        and grid[next_row][next_col] == 1
    ):
        grid[next_row][next_col] = 2
        queue.append((next_row, next_col))
        fresh -= 1

E a condição do meio é extremamente importante:

Confere se ainda estamos caminhando dentro da matriz - colunas e linhas válidas;
Confere se a posição atual é uma laranja e é fresca.

Se positivo, adicionamos ela na queue de laranjas podres e diminuímos a contagem de laranjas frescas.

Sem esquecer de atualizar o valor pra 2, pois garante que não adicionemos a laranja podre de volta na nossa queue.

E, pra finalizar, retornamos o valor de minutos:

return minutes if fresh == 0 else -1

Se ainda tiver laranjas frescas, então não foi possível apodrecer todas, retornando -1. Se não, retornamos o número de minutos passados.

Conclusão

Complexidade de tempo: O(m x n)
Precisamos iterar o board inteiro pra descobrir as laranjas, porém, apenas uma vez cada linha/coluna.

Complexidade de espaço: O(m x n)
Usamos uma queue que, no pior caso, vai ter uma matriz inteira cheia de laranjas podres.

Não é porque tem vários loops aninhados que a complexidade de tempo é quadrática. É preciso analisar, linha por linha, o que o código faz.

Esse desafio não é simples e eu demorei algumas horas pra concluir. E esse não foi o código final. Ao todo eu tentei submeter oito vezes na plataforma leetcode.