作者:袁宇韬
关键词:二分图
有一个的棋盘,每个格子与上、下、左、右、右上、左下六个格子相邻。给定其中的一些格子,问最少用多少种颜色可以对这些格子染色且相邻的格子颜色不同。
将坐标为的格子染成颜色可以用最多三种颜色完成染色。因此只要考虑能否用一种或两种颜色染色。
将需要染色的格子视为点,相邻的格子之间连边,则能用一种颜色染色的条件为图的每个连通分量大小为1,能用最多两种颜色完成染色的条件为图是二分图。
时间复杂度。