考虑这个问题:
定义了一个方形网格，每个方 block 要么可以通过(1)，要么不能通过(0)。 首先，我们在网格中有一个简单连接的空间，具有不可逾越的边界，如下所示:
然后我们开始将各种尺寸(例如 1x1、2x2...)的不可逾越障碍物放置到可通过的空间中。放置每个障碍物后，我们需要测试剩余的可通行空间是否仍然是连通的(即确保我们没有将可通行空间分割成两个或多个不连通的空间)。瓷砖也是对角连接的。
重点是，在放置每个障碍物之后，每个剩余的可通行方 block 都有一条将其连接到所有其他剩余可通行方 block 的路径。
我知道可以在可能断开的点之间搜索路径，但我担心这可能效率太低。我感兴趣的是尽快进行此测试。
感谢您的帮助!
最佳答案
实现洪水填充算法。作为执行填充的副作用，计算填充的方 block 数量。放置障碍物后，从任何空心方 block 开始执行另一次洪水填充，并将填充方 block 的数量与原始数量减去作为障碍物放置的方 block 数量进行比较。如果它们不相同，则区域已断开连接。
关于algorithm - 测试网格通过性，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9968979/