arrays - 确定网格上的点是否为 "trapped"(封闭)

Question

我有一个网格(如下例)，其中包含外墙(标记为 W)、环境 block (E)、开放空间 (o) 和事件点 (A)。目前，此网格存储在 [,] 中，其中包含与给定点关联的所有数据。我试图确定是否包含一个事件点(定义为无法到达网格顶部，因为它被环境 block 阻挡)，但我很难找到解决此问题的简单方法。我知道我可以实现 A* 并且使用所有示例代码它或多或少会很容易，但我认为对于这种看似微不足道的操作来说，性能损失真的没有必要或不值得。

W--Top Of Grid--W
W---------------W
W-EEAEE-----EEE-W
WEEEEEEE-EEEEAEEW
WEEEEEEE--EEEEEEW
WEEEEEEEE-AEEEEEW
WWWWWWWWWWWWWWWWW

往下第三行的 A 可以绘制一条通往网格顶部的路径，最后一行的 A 也可以，但是往下第四行的 A 不能。我不关心实际路径，我只需要确定对象是否被困。这个项目的最佳解决方案是什么？

就其值(value)而言，如果有帮助的话，它是一个用于回合制网格游戏的 C# 项目。

提前感谢您提供的任何帮助，非常感谢。

Answer 1

我认为顶部网格的填充将解决所有问题。从顶部淹没，然后检查哪个“A”被淹没:)

该算法保证在整个过程中每个节点只访问一次，在最坏的情况下不能更快。而且它真的很容易用任何语言实现。

这是来自 Wikipedia 的算法:

 Flood-fill (node, target-color, replacement-color):
 1. If the color of node is not equal to target-color, return.
 2. Set the color of node to replacement-color.
 3. Perform Flood-fill (one step to the west of node, target-color, replacement-color).
    Perform Flood-fill (one step to the east of node, target-color, replacement-color).
    Perform Flood-fill (one step to the north of node, target-color, replacement-color).
    Perform Flood-fill (one step to the south of node, target-color, replacement-color).
 4. Return.

...它看起来像:(来自 wiki)

简而言之:

1. 来自顶部网格的泛洪，“W”和“E”阻挡了泛洪(如图中的黑色单元格)
2. 洪水之后，检查有多少包含“A”的地方被洪水淹没。