Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

表示对于0K的代码很是抑郁。我用的爆搜竟然不超时

Posted by proverbs at 2012-05-01 22:01:27 on Problem 1606
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include <stack>
#define K 10000
using namespace std;
int a,b,c;
struct NOTE
{
	int voa,vob,pre,op;
}ans;
vector<NOTE> q;
bool vis[10010000];
void reset()
{
	memset(vis,0,sizeof vis);
	q.clear();
}
NOTE bfs()
{
	
	NOTE tmp,tp;
	int num;
	tmp.voa=0;tmp.vob=0;tmp.pre=-1;
	vis[a*K+b]=true;
	q.push_back(tmp);
	for(int i=0;i<q.size();i++)
	{
		NOTE sta=q[i];
		
		tp.voa=a;tp.vob=sta.vob;
		num=K*tp.voa+tp.vob;
		if(!vis[num])
		{
			tp.pre=i;tp.op=1;
			if(tp.vob==c) return tp;
			q.push_back(tp);
			vis[num]=true;
	    }
		
		tp.voa=sta.voa;tp.vob=b;
		num=K*tp.voa+tp.vob;
		if(!vis[num])
		{
			tp.pre=i;tp.op=2;
			if(tp.vob==c) return tp;
			q.push_back(tp);
			vis[num]=true;
	    }
		
		tp.voa=0;tp.vob=sta.vob;
		num=K*tp.voa+tp.vob;
		if(!vis[num])
		{
			tp.pre=i;tp.op=3;
			if(tp.vob==c) return tp;
			q.push_back(tp);
			vis[num]=true;
	    }
		
		tp.voa=sta.voa;tp.vob=0;
		num=K*tp.voa+tp.vob;
		if(!vis[num])
		{
			tp.pre=i;tp.op=4;
			if(tp.vob==c) return tp;
			q.push_back(tp);
			vis[num]=true;
	    }
		
		if(b-sta.vob>=sta.voa)
		{
			tp.voa=0;tp.vob=sta.voa+sta.vob;
		    num=K*tp.voa+tp.vob;
		    if(!vis[num])
		    {
				tp.pre=i;tp.op=5;
				if(tp.vob==c) return tp;
				q.push_back(tp);
				vis[num]=true;
	        }
		}
		else
		{
			tp.voa=sta.voa-(b-sta.vob);tp.vob=b;
		    num=K*tp.voa+tp.vob;
		    if(!vis[num])
		    {
				tp.pre=i;tp.op=5;
				if(tp.vob==c) return tp;
				q.push_back(tp);
				vis[num]=true;
	        }
		}
		
		if(a-sta.voa>=sta.vob)
		{
			tp.voa=sta.voa+sta.vob;tp.vob=0;
		    num=K*tp.voa+tp.vob;
		    if(!vis[num])
		    {
				tp.pre=i;tp.op=6;
				if(tp.vob==c) return tp;
				q.push_back(tp);
				vis[num]=true;
	        }
		}
		else
		{
			tp.voa=a;tp.vob=sta.vob-(a-sta.voa);
		    num=K*tp.voa+tp.vob;
		    if(!vis[num])
		    {
				tp.pre=i;tp.op=6;
				if(tp.vob==c) return tp;
				q.push_back(tp);
				vis[num]=true;
	        }
		}
	}
}
void print()
{
	stack<NOTE> st;
	NOTE x=ans;
	for(;;)
	{
		st.push(x);
		x=q[x.pre];
		if(x.voa==0&&x.vob==0) break;
	}
	while(!st.empty())
	{
		
		NOTE y=st.top();
		st.pop();
		if(y.op==1) printf("fill A\n");
		if(y.op==2) printf("fill B\n");
		if(y.op==3) printf("empty A\n");
		if(y.op==4) printf("empty B\n");
		if(y.op==5) printf("pour A B\n");
		if(y.op==6) printf("pour B A\n");
	}
	printf("success\n");
}
int main()
{
	while(scanf("%d%d%d",&a,&b,&c)!=EOF)
	{
		reset();
		ans=bfs();
		print();
	}
	system("pause");
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator