1614.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"stdio.h"
#include"queue"
#include"set"
#include"list"
using namespace std;

struct node
{
	enum {human,romulan,shield} kind;
	int l,u;
}v[100010];

int n,m;
list<int> e[100010];

void init()
{
	char w[100];
	int a,s,i,b;

	scanf("%d %d",&n,&m);
	
	scanf("%s",w);
	scanf("%d",&s);
	
	for(i=0;i<s;i++)
	{
		scanf("%d",&a);
		v[--a].kind=node::human;
		e[a].clear();
	}

	scanf("%s",w);
	scanf("%d",&s);

	for(i=0;i<s;i++)
	{
		scanf("%d",&a);
		v[--a].kind=node::romulan;
		e[a].clear();
	}

	scanf("%s",w);
	scanf("%d",&s);

	for(i=0;i<s;i++)
	{
		scanf("%d",&a);
		v[--a].kind=node::shield;
		e[a].clear();

		scanf("%d %d",&v[a].l,&v[a].u);
	}

	scanf("%s",w);
	scanf("%d",&s);

	for(i=0;i<s;i++)
	{
		scanf("%d %d",&a,&b);
		a--,b--;
		e[a].push_back(b);
	}

	return ;
}

set<int> s[1001];

struct bomb
{
	int q;
	int at;
};
queue<bomb> qu;

void doit()
{
	char w[100];
	int p,i,ans,begin,q,dq;
	list<int>::iterator iter;
	bool key;
	bomb b,bt;


	scanf("%s",w);
	scanf("%d",&p);

	ans=0;
	while(p--)
	{
		scanf("%d %d %d",&begin,&q,&dq);
		begin--;

		while(!qu.empty())qu.pop();
		for(i=0;i<=1000;i++)
			s[i].clear();

		b.q=q;b.at=begin;
		qu.push(b);
		s[b.q].insert(b.at);

		key=1;

		while(!qu.empty()&&key)
		{
			b=qu.front();
			qu.pop();

			for(iter=e[b.at].begin();iter!=e[b.at].end();iter++)
			{
				if(v[*iter].kind==node::romulan)
				{
					ans++,key=0;
					break;
				}
				else if(v[*iter].kind==node::human)
				{
					if(s[b.q].find(*iter)==s[b.q].end())
					{
						bt.at=*iter,bt.q=b.q;
						s[b.q].insert(bt.at);
						qu.push(bt);
					}
					if(v[b.at].kind==node::shield)
					{
						bt.q=b.q+dq,bt.at=*iter;
						if(bt.q<=1000&&s[bt.q].find(*iter)==s[bt.q].end())
						{	
							s[bt.q].insert(bt.at);
							qu.push(bt);
						}

						bt.q=b.q-dq;
						if(bt.q>=0&&s[bt.q].find(*iter)==s[bt.q].end())
						{	
							s[bt.q].insert(bt.at);
							qu.push(bt);
						}
					}
				}
				else 
				{
					bt.q=b.q;bt.at=*iter;
					if(bt.q<=v[bt.at].u&&bt.q>=v[bt.at].l&&s[bt.q].find(bt.at)==s[bt.q].end())
					{
						s[bt.q].insert(bt.at);
						qu.push(bt);
					}
					
					if(v[b.at].kind==node::shield)
					{
						bt.q=b.q+dq;
						if(bt.q<=v[bt.at].u&&bt.q>=v[bt.at].l&&s[bt.q].find(bt.at)==s[bt.q].end())
						{
							s[bt.q].insert(bt.at);
							qu.push(bt);
						}

						bt.q=b.q-dq;
						if(bt.q<=v[bt.at].u&&bt.q>=v[bt.at].l&&s[bt.q].find(bt.at)==s[bt.q].end())
						{
							s[bt.q].insert(bt.at);
							qu.push(bt);
						}
					}
				}
			}//for
		}//while

		
	}//while
	
	printf("%d\n",ans);
	
	return ;
}

int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		init();
		doit();
	}

	return 0;
}