首页 » 技术分享 » A - 熊猫病毒的攻击

A - 熊猫病毒的攻击

　
评论关闭　812次浏览
文章目录

最近几个月，计算机病毒在中国的网络中传播。这个病毒带有一只可爱的熊猫图标，因而得名熊猫病毒。使这种病毒难以处理的原因是它有很多变种。

不幸的是，我们实验室的网络也感染了熊猫病毒。从上图中可以看出，我们实验室中的计算机放置在M行和N列的矩阵中。计算机仅与其旁边的计算机连接。最初，T台计算机感染了熊猫病毒，每种病毒都有不同的变异（1型，2型...... T型）。网络中的每台计算机都具有特定的防御等级L（0 < L <1000）。熊猫病毒将根据以下规则迅速传播到网络中：

  1. 病毒只能通过网络从已感染的计算机传播到干净的计算机。
  2. 如果计算机已经被一种病毒变种感染，它将永远不会被另一种变异感染。
  3. 熊猫病毒的传播能力每天都在增加。在第1天，病毒仅感染具有防御级别1的计算机，前提是病毒可以传播到该计算机，但是，防御级别> 1的计算机将停止沿该路径传输。在D日，它可以传播到所有连接防御等级<= D的计算机，前提是传输没有被路径上防御等级> D的计算机停止。
  4. 在一天之内，类型1的病毒变异将首先传播并感染它可以到达的所有计算机。然后是类型2的病毒变种，然后是类型3等。

以下样本显示了上述感染过程：

一开始，只有2台计算机被感染：

1 0 0 0
0 0 0 2
0 0 0 0

在第1天：

1 0 0 0
0 0 0 2
0 0 2 2

在第2天：

1 0 1 0
1 1 1 2
0 1 2 2

在第3天：

1 1 1 1
1 1 1 2
1 1 2 2

最后，网络中的所有计算机都被病毒感染了。

您的任务是在所有计算机被感染后计算，有多少计算机感染了某些特定的病毒变体。

 

输入

 

输入包含多个测试用例！

在每个测试用例的第一行上有两个整数M和N（1 <= M，N <= 500），接着是M * N矩阵。正整数牛逼的矩阵表示相应的计算机已经被类型的病毒变体感染牛逼开头而负整数，-L表明计算机具有防御级别大号。然后有一个整数Q表示查询的数量。以下Q行中的每一行都有一个整数，这是我们关心的病毒变异类型。

 

产量

 

对于输入的每个查询，在单行中输出一个整数，表示受此类病毒变体攻击的计算机数。

 

样本输入

 

3 4
1 -3 -2 -3
-2 -1 -2 2
-3 -2 -1 -1
2
1
2

 

样本输出

 

9
3

深搜和优先队列

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

const int MAX=500+10;

struct node_t
{
    int day;    //天数
    int type;   //类型
    int level;  //级别
    int vis;    //是否访问过
    int x,y;    //坐标
    bool friend operator < (node_t a,node_t b)   //根据天数、类型排序的有限队列
    {
        if(a.day==b.day)
        {
            return a.type>b.type;
        }
        return a.day>b.day;
    }
}node[MAX][MAX];

priority_queue <node_t> q;
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};

int m,n;
int cnt[MAX*MAX]={0};

void bfs()  //深搜
{
    while(!q.empty())
    {
        node_t u=q.top();   q.pop();
        int minL=0;
        bool first=1;
        for(int d=0 ; d<4 ; ++d)
        {
            int nx=u.x+dx[d] , ny=u.y+dy[d];
            if(nx>=0 && nx<m && ny>=0 && ny<n)
            {
                node_t &v=node[nx][ny];
                if(v.vis==0)
                {
                    if(u.day>=v.level)
                    {
                        v.vis=1;
                        v.type=u.type;
                        v.day=u.day;
                        cnt[v.type]++;
                        q.push(v);   //入队
                    }
                    else
                    {
                        if(first)
                        {
                            first=0;
                            minL=v.level;
                        }
                        else
                        {
                            minL=min(minL,v.level);
                        }
                    }
                }

            }
        }
        if(minL)
        {
            u.day=minL;
            q.push(u);//if still has some node to visit
        }
    }
}

int main()
{
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        memset(cnt,0,sizeof cnt);
        for(int i=0; i<m ; ++i)
        {
            for(int j=0 ; j<n ; ++j)
            {
                node_t &x=node[i][j];
                int t;
                scanf("%d",&t);
                x.x=i; x.y=j;  //坐标输入
                if(t>0)        //病毒源
                {
                    x.day=1;
                    x.vis=1;
                    x.type=t;
                    cnt[t]++;
                    q.push(x);
                }
                else
                {
                    x.level=-t;
                    x.vis=0;
                }
            }
        }
        bfs();
        int q;         //查询
        scanf("%d",&q);
        while(q--)
        {
            int t;
            scanf("%d",&t);
            printf("%d\n",cnt[t]);
        }
    }
    return 0;
}

 

 

转载自原文链接, 如需删除请联系管理员。

原文链接：A - 熊猫病毒的攻击，转载请注明来源！

赞 0