c# - 检查二维数组中相连邻居的算法

Question

对于游戏 (WPF)，我需要创建一个 map 编辑器。 map 由 4x3 map 字段的矩阵定义。当用户编辑 map 时，他可以启用和禁用每个字段，以此定义 map 的外观。现在 map 只有在每个字段都连接到另一个字段时才有效。 IE。此 map 有效(蓝色为事件状态，灰色为非事件状态):

我有一个带有 map 字段的二维数组。每个字段都有一个 boolean 值，用于定义它是否处于事件状态。为了检查 map 是否有效，我编写了以下方法:

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 个事件字段或多于 1 个事件字段)。不幸的是，使用这种方法，以下 map 也是有效的:

但是这些 map 应该是无效的。检查 map 是否有效的最有效算法是什么？

Answer 1

一对方法:

执行BFS来自任何事件单元格，并在结束后检查所有事件单元格是否已标记

使用union-find data structure (你不需要对这么小的网格进行任何优化)，插入具有事件邻居的事件单元格，并检查是否只有一个连接的组件