Attack of Panda解题报告

    JDP给偶的题,只是想了下算法。具体程序还没编,等哪天郁闷了再编。

本题是一道模拟题,可以种子填充法(FloodFill)解决。题目简述如下:

在一个M´N的矩阵型计算机网络中,开始有若干台计算机携带病毒。在第一天,这些病毒的攻击力为1,这些病毒能传染给与之相邻的抵抗系数为1的计算机上,且被感染的计算机能够继续对其邻近的抵抗系数为1的计算机进行感染。以后每经过一天,这些携带病毒的计算机(包括开始就有病毒的和被传染的)的病毒攻击力就增加1。在第D天,病毒的攻击力就达到了D,这些病毒会扩散到相邻的、抵抗系数不超过过D的计算机上。病毒具有T个变种,问题是求在所有计算机被感染后,每个变种所感染的计算机数量。

在题中有几点问题需要注意:

初看此题,很容易想到种子填充算法。这道题与种子填充算法极其类似,但题目稍微变了形。我们将感染病毒的计算机作为种子,则开始时有若干个种子。但是题目说明病毒是按照顺序逐个感染其他计算机的,因此可以先用对各个种子按照顺序使用种子填充法(:应按照题中Q后输入病毒类型的顺序,而不是数字的顺序)。在第K天的填充过程中,只有抵抗系数小于或等于K的计算机,并且未被感染的计算机才能作为填充的对象。

在经过一天后,由于病毒能感染的计算机有所改变,因此要重新进行种子填充。我们可以以刚开始被感染的计算机作为种子重新进行填充。

不过,这样被感染的计算机就被搜索了很多遍,浪费了很多时间。因此需要进行优化。

在遇到不能被感染的计算机的情况下,我们可以将这个节点记录起来,并在下一次填充时直接将此节点作为种子重新填充,那么以前已经被感染到的计算机就不需要重新填充,节省了大量的时间。

此时,我们不需要以天作为界限进行填充,可以使用队列一次性进行填充,这样,我们需要记录在填充时每个种子所“发生”的时间。

这种方法称为优先队列的方法,具体实现如下:在无法感染的计算机中,寻找与被感染区域相邻的、最先被感染的计算机,并将其加入到队列。

实现算法简要叙述如下:

(1)定义一个优先队列p_queue,读入数据时,将所有被感染的计算机都加入到该队列中。

(2)定义一个变量com_quick记录当前无法感染、但最快被感染的计算机,初始时令com_quick=负无穷大。对该队列进行种子填充:令q=pop(p_queue),p为与q相邻的一台计算机,如果在该天(即q.cur_day)能对p进行感染(满足条件map[p.x][p.y]+q.cur_day>0),则令p=q,并将p加入队列,同时在map数组中标记被感染的计算机;如果不能感染p,则令com_quick=map[p.x][p.y]。

(3)在四个方向全部判断完毕后,如果com_quick不为负无穷大,则令q.day=-com_quick,并将q加入队列

(4)重复步骤2和步骤3,直到队列为空。

之后统计各种类型病毒所感染的计算机数(也可在填充过程中进行累加),输出即可得出答案。

By Lieo

2009/11/7

发表评论

电子邮件地址不会被公开。