二维数组中瓦片连接的算法
Algorithm for tile connection in a two-dimensional array
我有一个简单的 Tile-Class，其中有 属性 IsBlack。我正在使用 二维数组 (Tile[,]).
我想检查是否所有的白色字段（IsBlack=false）都已连接。以下示例将 return true:
而以下会 return false:
我有很多想法，但我认为它们效率很低：
- 运行 一种从每个瓦片之间寻找路径的算法（非常低效）
- 找到 "rectangles" 个黑色方块。 （比如第一张图有1个矩形，"border"）肯定只有1个。（不确定这个方法是否有效）
- 按光栅顺序搜索白色字段
- 运行 从那个点开始的 floodfill 算法并标记您访问过的图块
- 继续查找是否还有未标记为已访问的白色字段
如果步骤 3 找到未访问的白色，则 return 为假，否则 return 为真。
- 将您的结构呈现为图形：如果节点 A 和 B 在图块呈现中具有共同边，则存在节点 A 和 B 之间的边（假设不允许对角线移动）
- 运行DFS，记录下你接触过的节点
如果在 运行 2 之后缺少一些节点，则 space 被分区。
我有一个简单的 Tile-Class，其中有 属性 IsBlack。我正在使用 二维数组 (Tile[,]).
我想检查是否所有的白色字段（IsBlack=false）都已连接。以下示例将 return true:
而以下会 return false:
我有很多想法，但我认为它们效率很低：
- 运行 一种从每个瓦片之间寻找路径的算法（非常低效）
- 找到 "rectangles" 个黑色方块。 （比如第一张图有1个矩形，"border"）肯定只有1个。（不确定这个方法是否有效）
- 按光栅顺序搜索白色字段
- 运行 从那个点开始的 floodfill 算法并标记您访问过的图块
- 继续查找是否还有未标记为已访问的白色字段
如果步骤 3 找到未访问的白色，则 return 为假，否则 return 为真。
- 将您的结构呈现为图形：如果节点 A 和 B 在图块呈现中具有共同边，则存在节点 A 和 B 之间的边（假设不允许对角线移动）
- 运行DFS，记录下你接触过的节点
如果在 运行 2 之后缺少一些节点，则 space 被分区。