[CF 316F3]Suns and Rays解题报告

作者注

图片来自


题目大意

给出一张位图,是太阳和周围的光芒,像这样:

问有多少个太阳,并统计每个太阳周围的光线数量,排序后输出。
图的规模是1600*1600,光线的宽度<=3.保证太阳不会太小,光线也不会太短。

题解

这题挺有意思。
首先将白色“收缩”:如果一个点的周围有黑色,就将它变成黑的。重复若干次。


就变成了这样。

然后“扩张”,即逆操作:若周围有白的就把它变成白的。


(注意每个白色区域都变大了)

我们可以在这张图中找出所有太阳的“核心部分”,并给它们标号。

用原图减掉这张图,得到:



这样就把所有的光线独立了出来。对它们进行floodfill即可。

注意,最后可能有一些小块,判断一下,如果规模太小就不认为是光线即可。

代码


发表评论

电子邮件地址不会被公开。 必填项已用*标注