这是本文档旧的修订版!
给定一些黑格和一些白格,要求将一些白格转化为黑格,使得所有黑格连通但不出现环路。
题目保证以起始时以每个黑格为中心的 $3\times 3$ 范围内没有其他黑格。
当 $n\equiv 1\bmod 3$ 时,考虑将第 $1,4,7\cdots$ 行染成黑色,然后对第 $3k+2,3k+3$ 行的每列,最多只有一个黑格。
如果第 $3k+2,3k+3$ 行间存在黑格,直接将两行的任意一个黑格所在列全染黑,否则将两行的第一列染黑。易知这样即可完成构造。
当 $n\not\equiv 1\bmod 3$ 时,将 $1,4,7\cdots$ 行换成第 $2,5,8\cdots$ 行处理即可。