Al plantar flores en una maceta, es importante asegurarse de que cada vez que riegues la planta, el agua que no sea absorbida por las raíces se drene por el fondo de la maceta. De lo contrario, el agua se acumulará en el fondo de la maceta y hará que la planta se pudra.
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, *], ]Observe que la ruta incluye las filas superior e inferior. Movimientos permitidos: los únicos movimientos permitidos son arriba, abajo, izquierda y derecha. No se permiten diagonales.
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], ]Ambas soluciones funcionan, y ambas pueden implementarse utilizando solo una cantidad constante de memoria adicional, modificando la matriz en su lugar. Dado que la tarea es modificar la matriz, también puede aprovechar la capacidad de hacerlo.
BFS es un poco más simple y encontrará el camino más corto, no es un requisito, pero no podría hacer daño.