Choosing-not-to-be-adjacent cells: algorithm's time complexity

Question

There is an area made with N 1x1 squares, and all parts of area are connected (there are no inaccessible square from any square). Here are some examples of area.

I want to select some squares in this area, and two adjacent squares cannot be selected together(diagonally touching is not adjacent).

Can I find maximum quantity of selected squares within time complexity O(N)? And how can I do?

Thank you very much.

Answer 1

The problem you are talking about is called Maximum Independent Set. In all generality it is NP-hard, so you can't expect an efficient algorithm to find the best solution.

However, Maximum Independent Set in all generality is about selecting vertices in a graph. Your problem is about selecting squares in a grid; so your problem is a particular case of Maximum Independent Set. Hopefully, solving Maximum Independent Set restricted to your particular case might be easier than solving it in all generality.

It turns out, grid graphs are bipartite graphs. And Maximum Independent Set restricted to bipartite graphs is easy!

Here is a duplicate question on cs.stackexchange: https://cs.stackexchange.com/questions/3022/maximum-independent-subset-of-2d-grid-subgraph. The accepted answer links some algorithms.

Googling "maximum independent set on a grid" also gives some interesting results.