1. 首页
2. BFS
3. 本页

ZOJ 2849 Attack of Panda Virus (优先队列)

主要麻烦在每天等级会上升一级，，每次周围有不能感染的电脑，在该点找到最小能感染的等级入队就好了，然后按优先队列，先考虑等级，再考虑编号进行bfs。。。

#include<iostream>
#include<cstdio>
#include<string>
#include<string.h>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<iomanip>
#include<map>
#include<vector>
#include<queue>
#include<stack>
//#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int N = 1050;
const double PI = 3.1415926;

int mp[550][550];
int vis[550][550];
int dir[][2]= {1,0,-1,0,0,-1,0,1};
int n,m;
int cnt;
int ans[250010];

struct start
{
    int x,y;
    int bh;
} p[250010];

struct node
{
    int x,y;
    int bh;
    int level;
    int day;
    bool operator <(const node &b)const
    {
        if(level==b.level)
            return bh>b.bh;
        return level>b.level;
    }
} st,nx;

void solve()
{
    priority_queue<node>q;
    for(int i=0; i<cnt; ++i)
    {
        st.x=p[i].x;
        st.y=p[i].y;
        st.bh=p[i].bh;
        st.level=1;
        ans[st.bh]++;
        q.push(st);
    }
    while(!q.empty())
    {
        node tmp=q.top();
        q.pop();
        int ff=0;
        for(int i=0; i<4; ++i)
        {
            int xx=tmp.x+dir[i][0];
            int yy=tmp.y+dir[i][1];
            if( xx<0 || xx>=n || yy<0 ||yy>=m)
                continue;
            if(mp[xx][yy]>=0)
                continue;
            if(tmp.level>=(mp[xx][yy]*-1))
            {
                nx.x=xx;
                nx.y=yy;
                nx.bh=tmp.bh;
                nx.level=tmp.level;
                mp[xx][yy]=tmp.level;
                ans[tmp.bh]++;
                q.push(nx);
                continue;
            }
            if(!ff || mp[xx][yy]>ff)
            {
                ff=mp[xx][yy];
            }
        }
        if(ff!=0)
        {
            tmp.level=-ff;
            q.push(tmp);
        }
    }

    return ;

}


int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        memset(ans,0,sizeof(ans));
        cnt=0;
        for(int i=0; i<n; ++i)
        {
            for(int j=0; j<m; ++j)
            {
                scanf("%d",&mp[i][j]);
                if(mp[i][j]>0)
                {
                    p[cnt].x=i;
                    p[cnt].y=j;
                    p[cnt++].bh=mp[i][j];
                }
            }
        }
        solve();
        int que;
        scanf("%d",&que);
        int bd;
        for(int i=0; i<que; ++i)
        {
            scanf("%d",&bd);
            printf("%dn",ans[bd]);
        }
    }


    return 0;
}