ZOJ2849 Attack of Panda Virus 熊猫烧香~~ 优先队列+搜索

这题目很是坑爹，各种坑爹，一开始SF了不止多少次，后来发现是Type的不仅仅是1，2.而是到1000，还有给出的图 是500 * 500的，可是直接去搜索一直超时，想不通，题目给的是3000ms，早就够了可是不行，后来再改，又SF，不能忍了，就YY了一下，用优先队列把

总是做算法，不如来个陶冶情操的文章一篇： http://www.sanwen.net/subject/3628849/

题意：

给出一个矩阵，每一个元素代表一台电脑，每台电脑有一个值，这个值为了区分题目要求是负的，代表它能够抵御病毒几天，已经被一种病毒感染的电脑不会再被其它病毒感染，但是它无法阻拦其它病毒去感染其它电脑，然后有两种病毒｛1，2，3，....1000｝种的任意两种，Type类型值小的先去感染，但是肯定不同种类，第一天有两台电脑，病毒是可以传染的，第一天只能感染抵御一天的电脑，第二天才能感染只能抵御2天以及2天以下的，第三天能感染只能抵御3天以及3天以下的电脑，所有电脑被感染后  会有 Q个提问， 每一个提问  会问你 此病毒 最终感染了几台电脑

YY了一把优先队列，因为搜索一直超时改了SF所以感觉就是要优化， 按题意 很明显，抵御天数少的 放前面， 如果两台电脑抵御天数一样，病毒Type值小的 先去进行感染，这样优先条件就好了，然后 搜索一下，又举了 几个案例 过了 就交了一把 发现 RE，感觉自己程序写的没问题  也不会爆栈，所以说这道题目坑， 他没有明确的说明Q的范围，但是如果你开的Q的数组小于10^6的话，就是RE，所以这道题目坑点 数不胜数

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#define ll long long

using namespace std;

#define inf 10000000

int n,m;
int dir[4][2]={0,-1,0,1,1,0,-1,0};
int ans[5000000 + 5];
int mp[1000 + 5][1000 + 5];

void clear() {
	memset(ans,0,sizeof(ans));
	memset(mp,0,sizeof(mp));
}

typedef struct Node {
	int level;
	int type;
	int sx,sy;
	friend bool operator< (Node n1, Node n2) {
		if(n1.level == n2.level)
			return n1.type > n2.type;
		return n1.level > n2.level;
	}
};

priority_queue<Node> q; 

void dfs() {
	Node s,e;
	while(!q.empty()) {
		s = q.top();
		q.pop();
		int tmp = -inf;
		for(int i=0;i<4;i++) {
			int dx = s.sx + dir[i][0];
			int dy = s.sy + dir[i][1];
			if(dx <0 || dx >=n || dy<0 || dy>=m)continue;
			if(mp[dx][dy] > 0)continue;
			if(mp[dx][dy] + s.level >= 0) {
				e.sx = dx;
				e.sy = dy;
				e.type = s.type;
				ans[s.type]++;
				e.level = s.level;
				mp[dx][dy] = s.type;
				q.push(e);
			}
			else {
				if(mp[dx][dy] > tmp)
					tmp = mp[dx][dy];
			}
		}
		if(tmp != -inf) {
			s.level = -tmp;
			q.push(s);
		}
	}
}

int main() {
	while(scanf("%d %d",&n,&m) == 2) {
		clear();
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				scanf("%d",&mp[i][j]);
				if(mp[i][j] > 0) {
					Node node;
					node.sx = i;
					node.sy = j;
					node.type = mp[i][j];
					node.level = 1;
					q.push(node);
					ans[mp[i][j]]++;
				}
			}
		}
		dfs();
		int Q;
		scanf("%d",&Q);
		for(int i=0;i<Q;i++) {
			int a;
			scanf("%d",&a);
			printf("%d\n",ans[a]);		
		}
	}
	return 0;
}

ZOJ2849 Attack of Panda Virus 熊猫烧香~~ 优先队列+搜索,布布扣,bubuko.com

ZOJ2849 Attack of Panda Virus 熊猫烧香~~ 优先队列+搜索

原文：http://blog.csdn.net/yitiaodacaidog/article/details/21819673