P7479

· · 个人记录

先预处理出黑棋连通块的“气”。

给定的黑棋连通块会将整个棋盘划分出若干个空白连通块。而白棋只能放在这些空白连通块中。

如果存在一个空白连通块，它属于黑棋连通块的“气”，那么只有用白棋去填满这个空白连通块，才能使黑棋连通块在这个空白连通块的“气”变为 0 。

但是与此同时，白棋连通块的“气”也将变为 0 。若想让黑棋连通块在这个空白连通块的“气”变为 0 ，那么这个用白棋填满该空白连通块的一步只能是使整个黑棋连通块的“气”变为 0 的最后一步。

因此若想使黑棋连通块的“气”变为 0 ，必须至多只有一个空白连通块属于黑棋连通块的“气”。

若黑棋连通块的“气”覆盖了超过一个空白连通块，那么无论如何都不能使黑棋连通块的“气”变为 0 ，因为它的必要条件是用白棋填满任意一个属于黑棋连通块的“气”的空白连通块，而这是不合法的，因此不能满足。

若黑棋连通块的“气”覆盖了不超过一个空白连通块，则可以先将它的“气”未覆盖的空白连通块中的“气”全部吃掉，方法是以空白连通块中不是黑棋连通块的“气”的格子为白棋的“气”，不断蚕食黑棋连通块的“气”，这样一定是可以做到的。最后，若有一个属于黑棋连通块的“气”的空白连通块，则直接填满即可，过程一定可以做到合法。

现在代码写起来就比较容易了：直接bfs搜空白联通块，然后判断它是否属于黑棋连通块的“气”即可。然后统计，判断，这道题就做完了。