题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2849
题意：给定当前网络的病毒感染状态，求最终各编号病毒所能感染的电脑数。
给定一张N*M大小的地图（N,M<=500）。
地图内有T个为正数的点，表示初始病毒所在位置以及对应病毒的编号。
剩下的负数点表示所在位置电脑的安全等级。
求最终状态各病毒所能感染的电脑数目。
感染规则如下：
1、电脑只能被一种病毒感染。
2、存在一个天数d，只有（d+当前位置的电脑安全等级）>=0时该电脑才能被感染。
3、编号小的病毒优先行动，只有低编号的病毒不能再进行感染时才轮到髙编号的病毒行动。
思路：优先队列直接搞，结构体存下当前位置信息外加一个天数，优先队列先按天数排，后按病毒编号排。
注意在天数更改的时候不能让天数++，而应变为最低有效天数，不然就T。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <limits.h> #include <malloc.h> #include <ctype.h> #include <math.h> #include <string> #include <iostream> #include <algorithm> #include <queue> using namespace std; #define maxn 505 #define LL long long #define PI 3.141592653 struct node { int gl; int x,y; int d; bool operator < (const node &a) const { if(a.d!=d) return d<a.d; return gl>a.gl; } }; priority_queue<node>q; int mp[maxn][maxn]; bool vis[maxn][maxn]; int ans[maxn*maxn]; int n,m; int xx[4]={0,0,1,-1}; int yy[4]={1,-1,0,0}; void bfs() { while(!q.empty()) { node f=q.top(); // cout<<f.x<<" "<<f.y<<" "<<f.gl<<" "<<f.d<<endl; q.pop(); int flag=-1000000; for(int i=0;i<4;i++) { int dx=f.x+xx[i]; int dy=f.y+yy[i]; if(dx>=0&&dx<n&&dy>=0&&dy<m&&mp[dx][dy]&&vis[dx][dy]==false) { // cout<<f.x<<" "<<f.y<<" "<<f.gl<<endl; if(mp[dx][dy]>=f.d) { vis[dx][dy]=true; node nx; nx.gl=f.gl; nx.x=dx; nx.d=f.d; nx.y=dy; q.push(nx); ans[f.gl]++; } else { flag=max(flag,mp[dx][dy]); } } } if(flag!=-1000000) { f.d=flag; q.push(f); } } } int main() { while(cin>>n>>m) { memset(ans,0,sizeof(ans)); memset(vis,false,sizeof(vis)); while(!q.empty()) q.pop(); for(int i=0;i<n;i++) for(int j=0;j<m;j++) { cin>>mp[i][j]; if(mp[i][j]>0) { vis[i][j]=true; node tt; tt.gl=mp[i][j]; tt.x=i; tt.y=j; tt.d=-1; q.push(tt); ans[tt.gl]++; } } bfs(); int qu; cin>>qu; while(qu--) { int id; cin>>id; cout<<ans[id]<<endl; } } return 0; }