DEV Community

Cover image for Resolvendo o "Rotting Oranges"
Maurício Antunes
Maurício Antunes

Posted on • Updated on

Resolvendo o "Rotting Oranges"

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:

duas laranjas podres posicionadas em cantos opostos, uma no canto inferior esquerdo e outro no canto superior direito, próximas de outras laranjas frescas e espaços vazios

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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.

Top comments (2)

Collapse
 
cyytrus profile image
Paulo Castro

Cara, você é muito bom, a explicação ficou super didática!

Collapse
 
mauricioabreu profile image
Maurício Antunes

Muito obrigado pelo elogio! Me dá forças pra continuar escrevendo