[Codeforces 432E] Square Tiling

Description

给一个N\times M的矩阵,每次给一个正方形染色,要求每次染色的正方形四周已经染色的格子的颜色不能与即将染的颜色相同,按列优先把最终染的颜色排成一个字符串,要求这个字符串字典序最小。N,M\leq100

Solution

见过黄金分割比的图形吧,然后这题就SB了

我们按照那种方式进行染色,每次选相邻没有被用的最小的字母填入

但是有一个漏洞就是说如何判断是填正方形还是填一个单位

显然只需要判断[i-1,j],[i,j-1]即可,如果出现了上方的字符与当前要填入的字符中有空缺的情况,不如只填一个。

时间复杂度O(n\times m)

 

发表评论