2023.6.8 铺瓷砖

发布时间 2023-06-08 13:00:41作者: 烤肉kr

image

这个问题是一个NP-完全问题,所以基本上只能用爆搜的方法去做,从数据范围是13x13也可以看出来,在暗示用爆搜去做。

从大到小枚举正方形的长度k,尝试把这个正方形的左上角放到\((x, y)\)处。
如果\((x,y)\)已经被其他正方形覆盖了,就尝试\((x,y+1)\)。否则,放置成功,调到\((x,y+k)\)处继续尝试放置。

//todo