http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1849
//1833420 2009-04-14 16:41:33 Memory Limit Exceeded 2849 C++ 0 32769 aslys //1835799 2009-04-17 09:10:34 Accepted 2849 C++ 780 8292 aslys #include<iostream> #include<queue> using namespace std; struct Node { int vi; int vj; int day; int type; friend bool operator < (Node a,Node b) { if(a.day != b.day) return a.day > b.day; else return a.type > b.type; } }; priority_queue<Node>Q; int dir[4][2] = {-1,0,1,0,0,-1,0,1}; int m,n; int gra[501][501]; int sum[250002]; void init() { int i,j; Node p; memset(sum,0,sizeof(sum)); //一定要全部清空,切记切记 for(i=1;i<=m;i++) { for(j=1;j<=n;j++) { scanf("%d",&gra[i][j]); if(gra[i][j] > 0) { p.vi = i; p.vj = j; p.day = 1; p.type = gra[i][j]; Q.push(p); sum[gra[i][j]] ++; } } } }
void bfs() { int k,dmax; Node p,q; while(!Q.empty()) { q = Q.top(); Q.pop(); dmax = -111111111; for(k=0;k<4;k++) { p.vi = q.vi + dir[k][0]; p.vj = q.vj + dir[k][1]; if(p.vi>=1 && p.vi<=m && q.vi>=1 && q.vj<=n ) { if(gra[p.vi][p.vj] < 0 ) { if( gra[p.vi][p.vj] + q.day >= 0) { p.type = q.type; p.day = q.day; gra[p.vi][p.vj] = p.type; Q.push(p); sum[p.type] ++; } else if(gra[p.vi][p.vj] > dmax)//寻找其周围最快传染的机子~ { dmax = gra[p.vi][p.vj] ; } } }//for(k=0;k<4;k++) } if(dmax != -111111111) { q.day = dmax * (-1); Q.push(q); } }//while(!Q.empty()) } int main() { int a,T; while(cin>>m>>n) { init(); bfs(); cin>>T; while(T--) { scanf("%d",&a); printf("%d\n",sum[a]); } } return 0; }
|