zoj_1002(Fire Net)的一个简单的解法

做了一天,把此题AC了,看到网上用的算法很复杂,发个自己的出来。
思路:
1.如果城市全空,可以不管顺序,随便从哪里开始放“碉堡”,把“碉堡”射程里的城市标记下,后面的“碉堡”不放在这里即可得到结果。
2.但是如果城市中有“墙”的话,就不可以按照1的方法了,因为放置数量的多少与顺序是有关的,所以,怎样来确定这个顺序是很重要的。观察发现,城市里的空地按照领域中的“墙”的数量可以分为五种,即从0到4。再观察,可以得到这样一个结论:按邻域中墙的数目由多到少,往空地上安放“碉堡”,可以使数目最大!
于是按照这个结论,编程如下:
Continue reading “zoj_1002(Fire Net)的一个简单的解法”