[EC Final 2020] Fillomino

· · 题解

首先可以发现人类可以轻松解决这个问题，但是完全不知道怎么写。

解的数量显然很多，看上去你随便构造一个都是对的。

可以发现，如果只有两个颜色，似乎更好构造一点，于是考虑先确定一个颜色。

要让剩余两个颜色很可能合法，则第一个颜色构成的图形要尽量规则。

把第一个颜色平移到右下角。可以感受到填成长方形似乎比较优。

于是考虑划定一个长方形区域，在这个区域内一层一层填。

可以发现，这三种区域看起来比较对。

如果矩形太小，可以通过平移，使得把第一种颜色的起点移到最左边或最上边，直到存在比较大的矩形。

在这些矩形中随便取一个，把第一种颜色填完，转化为两种颜色的问题。

以 c 比较小的颜色为起点 BFS，为了不把最后一种颜色围起来，可以优先扩距离最后一个颜色出发点最远的点，用优先队列维护。

这么做完后还是有很大的概率出错，于是我们考虑随机化。

每次随机一个颜色作为第一种颜色，扩展的时候如果有权重相同的随机选一个取出来。填的时候随机横着填或竖着填。

进行一些乱搞后可以通过。

code