题解：P7171 [COCI 2020/2021 #3] Selotejp
可以做到 poly n。
考虑每次涂色的部分可以视作一条链，边点容斥，那么我们需要最小化总点数减去涂色的边数。注意只有相邻两个点都是 '#' 的边才能被染色，于是我们只保留这样的边。只有 '#' 需要被染色，于是我们只保留这样的点。
初始化答案为总点数减去总边数，那么我们需要最大化染色的边数。
考虑限制为每个点至多被染色一次，也就是一个点只能被一个方向的边（横边或者竖边）染色。
于是考虑边转点，对于共顶点，且不是同一方向的边，要求这两条边不能同时被染色，在这两条边之间连一条边即可。那么最大被染色边数就是连出来的二分图的最大独立集。