在花盆里種花時，重要的是要確保每當你給植物澆水時，任何未被根部吸收的水都會從花盆底部排出。否則，水會積聚在鍋底，導致植物腐爛。
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, *],
]
請注意，路徑包括頂行和底行。允許的移動：唯一允許的移動是向上、向下、向左和向右。不允許使用對角線。
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],
]
uj5u.com熱心網友回復：
兩種解決方案都有效，并且都可以通過在適當的位置修改矩陣來使用恒定數量的額外記憶體來實作。由于任務是修改矩陣，您不妨利用這樣做的能力。
BFS 稍微簡單一些，并且會找到最短路徑——不是必需的，但不會造成傷害。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/411533.html
標籤：