检查二维数组中相邻元素是否连接的算法

Question

我需要创建一个地图编辑器来制作一个(WPF)游戏的地图。地图由4x3个地图字段的矩阵定义。用户编辑地图时，可以启用或禁用每个字段，从而定义地图的外观。现在，只有当所有字段都与另一个字段连接时，地图才是有效的。例如，这张地图是有效的(蓝色为活动状态，灰色为非活动状态):

我有一个二维数组，其中包含地图字段。每个字段都有一个布尔值，用于定义它是否处于活动状态。为了检查地图是否有效，我编写了以下方法:

private bool IsMapPlayable()
{
    int numberOfActiveFields = 0;
    for (var row = 0; row < this.GameFields.Length; row++)
    {
        for (var col = 0; col < this.GameFields[row].Length; col++)
        {
            if (!this.GameFields[row][col].IsActive) continue;
            numberOfActiveFields++;

            if (!(row > 0 && this.GameFields[row - 1][col].IsActive)
                && !(row + 1 < this.GameFields.Length && this.GameFields[row + 1][col].IsActive)
                && !(col > 0 && this.GameFields[row][col - 1].IsActive)
                && !(col + 1 < this.GameFields[row].Length && this.GameFields[row][col + 1].IsActive)
                && numberOfActiveFields > 1)
            {
                return false;
            }
        }
    }

    return numberOfActiveFields > 0;
}

该方法仅检查每个字段是否具有直接活动邻居字段（并且具有1个活动字段或多个活动字段）。不幸的是，使用此方法，以下地图也是有效的： 但这些地图不应该是有效的。最有效的算法是检查地图是否有效？

- Kevin Brechbühl

---

每个地图是否总是以左上角的方格作为活动状态开始？ - Chris Haas

不，您可以根据需要定义地图。因此，它也可以仅激活[2] [2]和[2] [3]字段。 - Kevin Brechbühl

一个字段可以连接到超过两个其他字段吗？例如，[2] [2] 可以连接到 [1] [2]、[2] [1] 和 [2] [3] 吗？ - bebleo

@JamesWarne 是的，它可以。 - Kevin Brechbühl

Answer 1

一对方法：

从任何一个活动单元执行 BFS，结束后检查所有活动单元是否被标记

使用 并查集数据结构（对于这样小的网格，您不需要进行任何优化），将具有活动邻居的活动单元插入，并检查是否只有一个连通分量

- MBo

---

BFS正是我所需要的。谢谢！ - Kevin Brechbühl