Empresas
Empregos
  • Sobre nós
  • Soluções
    • Publicação de vagas
      Publique sua vaga e receba candidatos qualificados em 48h.
    • Avaliações de candidatos
      Mais de 500 testes técnicos e psicológicos, mais anti-fraude.
    • Headhunting
      Busca executiva personalizada do início ao fim.
    • Folha de Pagamento + EOR
      Dispersão de folha e EOR em mais de 15 países da LATAM.
  • Preços
  • Empregos

0

138
Visualizações
What should be the best approach for this algorithm? DFS or BFS? and why?

When planting flowers in a pot, it's important to make sure that whenever you water your plant any water that doesn't get absorbed by the roots drains out the bottom of the pot. Otherwise, the water will pool in the bottom of the pot and cause your plant to rot.

You recently decided to plant some flowers of your own,
and decided to fill the base of the pot with gravel. You've
decided to write code to verify whether water will
successfully drain out of the pot.
Using a 2D array to represent your pot, individual pieces of
gravel are notated with a 1 and empty spaces between
gravel are notated with a 0.
Example Pot #1:

[
[0, 1, 1, 1, 1],
[0, 1, 0, 0, 0],
[0, 0, 0, 1, 0],
[1, 1, 1, 1, 0],
[1, 0, 0, 1, 0],
]

Write a function to determine whether the water can fall
from the top row to the bottom, moving through the
spaces between the gravel. Taking the example pot from
above, you can see the posible path, which is marked by
replacing the relevant 0's with asterisks (*)

[
[*, 1, 1, 1, 1],
[*, 1, *, *, *],
[*, *, *, 1, *],
[1, 1, 1, 1, *],
[1, 0, 0, 1, *],
]

Notice that the path includes both the top and bottom rows. Allowed moves: The only moves allowed are up, down, left, and right. Diagonals are not allowed.

Here are a few pots that don't drain properly, along with
explanations.

[
[1, 1, 1],
[1, 1, 0],
[1, 0, 0],
]

Explanation: The top row has no gaps

[
[1, 1, 0],
[1, 1, 0],
[1, 1, 1],
]

Explanation: The bottom row has no gaps
[
[1, 1, 0],
[1, 1, 0],
[1, 0, 1],
]
about 4 years ago · Juan Pablo Isaza
1 Respostas
Responde à pergunta

0

Both solutions work, and both can be implemented using only a constant amount of extra memory, by modifying the matrix in place. Since the task is to modify the matrix, you might as well take advantage of the ability to do this.

BFS is a little simpler, and will find the shortest path -- not a requirement, but couldn't hurt.

about 4 years ago · Juan Pablo Isaza Relatório
Responde à pergunta
Encontrar trabalhos remotos

Descubra a nova forma de encontrar um emprego!

melhores empregos
Principais categorias de trabalho
Empresas
Postar vaga Preços Comercial
Jurídico
Termos e Condições Política de privacidade
© 2026 PeakU Inc. All Rights Reserved.
Andres GPT
Recomende algumas ofertas para mim
Preciso de ajuda