熊猫烧香 数据结构

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

struct Computer {     Computer():level(0),type(0),attack(0) {}     int level;     int type;     int attack; };

struct Virus {     Virus():x(0),y(0),type(0) {}     Virus(int a, int b, int c):x(a),y(b),type(c) {}     int x,y,type; }; const int MAXN = 510; Computer G[MAXN][MAXN]; int res[MAXN]; int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}}; int M,N,cnt,Q; vector<Virus> Store;

bool cmp(const Virus &a, const Virus& b) {     return a.type < b.type; }

void getPoint() {     Store.clear();     for(int i = 1; i <= M; ++i)     {         for(int j = 1; j <= N; ++j)         {             if(G[i][j].type)             {                 Store.push_back(Virus(i,j,G[i][j].type));             }         }     }     sort(Store.begin(),Store.end(),cmp); }

void dfs(int row, int col) {     int tx,ty;     for(int k = 0; k < 4; ++k)     {         tx = row + dir[k][0];         ty = col + dir[k][1];         if(tx < 1 || ty < 1 || tx > M || ty > N)             continue;         //如果没被感染并且可以攻击         if(G[tx][ty].type == 0 && G[row][col].attack >= G[tx][ty].level)         {             cnt--;             G[tx][ty] = G[row][col];             dfs(tx,ty);             G[tx][ty].attack++;         }     } }

void solve() {     while(cnt)     {         getPoint();         for(int i = 0; i < Store.size(); ++i)         {             //先进行dfs，dfs之后就是第二天了，这时候病毒的攻击力提升             dfs(Store[i].x,Store[i].y);             G[Store[i].x][Store[i].y].attack++;         }     }

    for(int i = 1; i <= M; ++i)     {         for(int j = 1; j <= N; ++j)             res[G[i][j].type]++;     } }

void init() {     memset(res,0,sizeof(res));     memset(G,0,sizeof(G));     Store.clear(); }

int main() {         int num;     while(cin >> M >> N && M+N)     {         init();         cnt = M*N;         for(int i = 1; i <= M; ++i)         {             for(int j = 1; j <= N; ++j)             {                 cin >> num;                 //病毒初始攻击力都为1，只能攻击防御力为1的机子                 //每过一天，攻击力+1                 //num > 0 表示这台机子被感染了，num表示病毒类型                 if(num > 0)                 {                     cnt--;                     G[i][j].type = num;                     G[i][j].attack = 1;                     //Store.push_back(Virus(i,j,G[i][j].type));                 }                 //num < 0 表示这台机子没被感染，num为防御力                 //因为这时num < 0 ，所以取相反数                 else                 {                     G[i][j].level = -num;                 }             }         }         sort(Store.begin(),Store.end(),cmp);         solve();         cin >> Q;         while(Q--)         {             cin >> num;             cout << res[num] << endl;         }     }     return 0; }