题意

$N \times N$ 的网格，每个格子染成红绿两色之一，给定边缘格子的颜色，问是否存在一种染色方案满足如下限制：

• 部分两个未染色格子之间有灰色标记（由输入给定），表示相邻的这两个格子必须染相同的颜色。
• 不存在相邻的 $2 \times 2$ 的子网格满足两组对角方格分别颜色相同。

数据范围：$3 \leq N \leq 30$。

题解

第二个限制等价于任意 $2 \times 2$ 的子网格都满足相邻且不同的格子对数量正好为 $2$。这相当于每个 $2 \times 2$ 的子网格都要与正好两个 $2 \times 2$ 的子网格匹配，任意匹配都相当于相交的两格不同。

由于只有相邻的可以匹配，所以可以按照奇偶性分为两部分。接下来考虑建立网络流：

• 每个 $2 \times 2$ 的子网格都是一个结点，与源点或汇点连一条流量为 $2$ 的边。
• 若相邻两个方格不受到第一条限制，那么连一条流量为 $1$ 的边。
• 对于边界上的相邻情况，那么只需要将与源点或汇点的流量减去 $1$。

只需要判断网络流是否能满流即可，时间复杂度 $\mathcal{O}(\text{poly}(n))$。