考虑此问题：测试网格通过性
定义了一个方形网格，每个网格可以是可通过的（1）或不可通过的（0）。 起初，我们在网格中的单连通有不可逾越的边界，就像这样：
然后，我们开始将各种尺寸的不可逾越的障碍物（例如的1x1，2x2的，..）进可以通行的空间。在放置每个障碍物后，我们需要测试剩余的可通行空间是否仍然连接（即确保我们没有在两个或多个断开的空间中拆分可通行空间）。瓷砖也是对角连接的。
问题在于，在每个障碍物放置之后，每个剩余的可通过的瓦片都有一条路径将其连接到每个剩余的可通过的瓦片。
我知道在可能断开的点之间搜索路径的可能性，但恐怕这可能太低效了。我感兴趣的是尽可能快地做这个测试。
感谢您的帮助！
实现洪水填充算法。作为执行填充的副作用，请计算填充的正方形数量。放置障碍物后，从任何开放方块开始执行另一次填充填充，并将填充方块的数量与原始数量减去作为障碍物放置的方块数量进行比较。如果他们不一样，你有断开连接的区域。
Wikipedia says这可以通过使用不相交集数据结构在分期偿还O（| V |）时间内完成，其中V是可通行空间（该部分的第二段）中元素的数量。引用是this paper。
这与Benjamin's answer具有相同的渐近复杂性，可能难以实现，所以我愿意这样做。 :)
此解决方案适用于*添加*顶点而不移除*它们。但是，如果它可以以某种方式用于去除边缘，那么它将比'O（| V |）'更有效。你将会第一次预处理'O（| V |）'，但是对于每个障碍物的添加 - 它会比'O（| V |）'快得多。它将是'O（alpha（n））'，其中'alpha'是相反的[ackerman函数]（http://en.wikipedia.org/wiki/Ackermann_function），对于每个实际输入，它都小于4。但我不确定你是否可以利用它来删除边缘。 – amit 2012-04-01 23:01:19
好点，我正在阅读sloppily。我真的不知道是否有办法使用联合发现（与其逆阿克曼运行时）去除边缘....它需要某种技巧，如构建一个双图（不，那不工作）。 – Dougal 2012-04-01 23:53:45
_Seems合法._ :) 谢谢！ – vedran 2012-04-01 22:48:53