This content originally appeared on DEV Community and was authored by Maurício Antunes
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.
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.
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
-
minutespra guardar o resultado final; - E
freshpra 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 ou não ter mais laranjas frescas, precisamos continuar adicionando 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.
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.
This content originally appeared on DEV Community and was authored by Maurício Antunes
Maurício Antunes | Sciencx (2024-07-18T23:08:00+00:00) Resolvendo o “Rotting Oranges”. Retrieved from https://www.scien.cx/2024/07/18/resolvendo-o-rotting-oranges/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.