このアルゴリズムの最良のアプローチは何でしょうか? DFSまたはBFS?なぜ?

-1
2022.01.15

鉢に花を植えるとき、植物に水をやるたびに根に吸収されない水が鍋の底を排出することを確認することが重要です。それ以外の場合は、水がポットの底に溜まり、植物が腐敗する原因となります。

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],
]
回答
2
2022.01.15

どちらのソリューションも機能し、マトリックスを適切に変更することで、一定量の余分なメモリのみを使用して実装できます。この作業はマトリックスの変更であるため、この操作を行う機能を利用する場合もあります。

BFSは少し簡単で、要件ではなく、傷つけることができなかった最短の道を見つけるでしょう。