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
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int vi;
int vj;
int day;
int type;
friend bool operator < (Node a,Node b)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if(a.day != b.day)
return a.day > b.day;
else
return a.type > b.type;
}
};
priority_queue<Node>Q;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int dir[4][2] = {-1,0,1,0,0,-1,0,1};
int m,n;
int gra[501][501];
int sum[250002];
void init()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int i,j;
Node p;
memset(sum,0,sizeof(sum));
//一定要全部清空,切记切记
for(i=1;i<=m;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
for(j=1;j<=n;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
scanf("%d",&gra[i][j]);
if(gra[i][j] > 0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
p.vi = i;
p.vj = j;
p.day = 1;
p.type = gra[i][j];
Q.push(p);
sum[gra[i][j]] ++;
}
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void bfs()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int k,dmax;
Node p,q;
while(!Q.empty())
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
q = Q.top();
Q.pop();
dmax = -111111111;
for(k=0;k<4;k++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
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 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if(gra[p.vi][p.vj] < 0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if( gra[p.vi][p.vj] + q.day >= 0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
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)//寻找其周围最快传染的机子~
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
dmax = gra[p.vi][p.vj] ;
}
}
}//for(k=0;k<4;k++)
}
if(dmax != -111111111)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
q.day = dmax * (-1);
Q.push(q);
}
}//while(!Q.empty())
}
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int a,T;
while(cin>>m>>n)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
init();
bfs();
cin>>T;
while(T--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
scanf("%d",&a);
printf("%d\n",sum[a]);
}
}
return 0;
}
|