codeforces #375 D. Lakes in Berland (dfs)

题目链接

题意:n*m个格子,有*和.两种类型。定义一个湖为边相邻的只有.组成的最大点集合,且任何一个.不在边界上。现在给出一个n*m的图保证至少有k个湖。问填多少个.成*,才能使得恰好有k个湖。

思路:贪心,先处理出所有的湖的大小,然后从小往大填。

注意dfs的时候如果某个“可能”的湖遇到了边界,要把之前打的标记撤销掉。

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz