选择不相邻的单元格：算法的时间复杂度
有一个由 N 个 1x1 方格组成的区域，并且该区域的所有部分都是相连的（没有任何方格无法到达的方格）。下面是一些面积的例子。
我想在这个区域中选择一些方块，并且两个相邻的方块不能一起选择（对角接触是不相邻的）。
我可以在时间复杂度 O(N) 内找到最大数量的选定方块吗？我该怎么办？
非常感谢。
您所说的问题称为最大独立集。一般来说，它是 NP 困难的，所以你不能指望一个有效的算法来找到最佳解决方案。
然而，最大独立集总的来说是关于选择图中的顶点。你的问题是在网格中选择方块；所以你的问题是最大独立集的特殊情况。希望解决仅限于您的特定情况的最大独立集可能比解决所有一般性问题更容易。
事实证明，网格图是二分图。限制二分图的最大独立集很容易！
这是 cs.stackexchange 上的重复问题：https://cs.stackexchange.com/questions/3022/maximum-independent-subset-of-2d-grid-subgraph。接受的答案链接了一些算法。
谷歌搜索“网格上的最大独立集”也给出了一些有趣的结果。