我正在使用具有两种状态“开”和“关”的正方形网格。我有一个相当简单的Connected Component Labeling算法，它可以找到所有“ON”组件。通常，但不总是，只有一个“ON”组件。
我希望构建一个算法，该算法将开/关单元格矩阵、组件标记（可能格式化为单元格的哈希集列表）以及自标记形成以来已更改的单元格列表作为输入，并输出一个新的标签。显而易见的解决方案是从头开始重新计算，尽管这效率不高。通常，已更改的单元格列表会很小。
在更改列表只是已打开的单元格的情况下，这很容易做到：
Groups G;
Foreach changed cell C:
Group U = emptygroup;
U.add(C);
Foreach Group S in G:
if (S contains a cell which is adjacent to C)
G.Remove(S);
U.UnionWith(S);
G.add(C);
但是，如果更改包含任何已关闭的单元格，我不知道该怎么做。请记住，所有 ON 单元格必须恰好是一个组的成员。因此，一种解决方案是获取与新关闭的单元格相邻的每个单元格，并查看它们是否相互连接（例如，使用 * 寻路）。这将产生 1-4 个连续的组（除非该单元是其组中唯一的单元，因此有 0 个相邻单元要检查，在这种情况下它会产生 0 个组）。然而，这仅比从头开始好一点，因为通常（但不总是）将这些相邻的方格连接在一起就像找到一个连续的组一样困难（除非有人建议用一种聪明的方法来做到这一点）。此外，如果有很多更改的单元格，这有点可怕……尽管我承认通常没有。
上下文，对于那些坚持知道我为什么这样做的人：Nurikabe谜题中的一个规则是你可能只有一组连续的墙。上面是我试图解决以提高速度（并玩寻路）的问题的简化。基本上，我希望检查连续的墙壁，而不会浪费从以前的此类测试中获得的信息。我想看看我的求解器中有多少地方可以利用以前的信息来提高速度，因为当 O(f(Δ)) 时使用 O(f(N)) 算法似乎有点痛苦算法就足够了（N 是拼图的大小，Δ 是自上次运行算法以来所做的更改）。
剖析确实表明改进此算法会影响执行时间，但这是一个有趣的项目，而不是为了利润，所以它并不重要，除了能够衡量更改是否有任何影响。
注意：我省略了解释我当前的算法，但它基本上通过在它找到的第一个 ON 方格上执行基于堆栈的Flood Fill算法来工作，然后检查是否还有更多 ON 方格（这意味着有多个组，它不会费心检查）。
编辑：增强想法：Yairchu 和 John Kugelman 的建议在我的脑海中形成了这种改进，这实际上并不是这个问题的解决方案，但可能会使这部分代码和其他几段代码运行得更快：
电流回路：
foreach (Square s in m.Neighbors[tmp.X][tmp.Y])
{
if (0 != ((byte)(s.RoomType) & match) && Retval.Add(s)) curStack.Push(s);
}
改进思路：
foreach (Square s in m.NeighborsXX[tmp.X][tmp.Y])
{
if (Retval.Add(s)) curStack.Push(s);
}
这将需要维护几个 m.NeighborsXX 实例（一个用于需要增强的每种匹配类型）并在正方形发生变化时全部更新它们。我需要对此进行基准测试，看看它是否真的有帮助，但它看起来像是用一些内存换取一些速度的标准案例。