[AGC004C] AND Grid

题意

给定一张黑白网格图，每个格子有两个颜色，保证边界没有黑色。

你需要另外构造两张网格图，使得两张黑色格子四联通，且两个网格黑色的交刚好等于原图。

\(n \le 500\)。

Sol

很好玩的构造题。

注意到边界没有黑色格子。

不难往这个方向想：先染满，使用某种方式将整张图分成两半，这样满足原图的性质只需要在对应白点多染色就行。

因此问题变为，构造一张图，使得她和她的相反图的所有白点都与至少一个黑点相邻，并且所有黑点联通。

不难想到直接对行奇偶分组，因为原图不会染边界，因此只需要给第一张图染第一列，给第二张图染最后一列即可。

复杂度：\(O(n ^ 2)\)。