#include <iostream>
#include <vector>
#include <queue>
using namespace std;
bool v[110][110];
int a,b,c;
struct pot
{
	int a,b;
	vector<pair<int,int> >vec;//记录路径,,pour(1,2)记为(1,2),drop(1)记为(1,4),fill(1)记为(1,3)
	pot(int aa,int bb):a(aa),b(bb){}
};
void output(vector<pair<int,int> >&vec)
{
	cout<<vec.size()-1<<endl;
	int i;
	for(i=1;i<vec.size();i++)
	{
		if(vec[i].second==3)
			cout<<"FILL("<<vec[i].first<<')'<<endl;
		else if(vec[i].second==4)
			cout<<"DROP("<<vec[i].first<<')'<<endl;
		else
			cout<<"POUR("<<vec[i].first<<','<<vec[i].second<<')'<<endl;
	}
}
int main()
{
	cin>>a>>b>>c;
	memset(v,false,sizeof(v));
	v[0][0]=true;
	pot temp(0,0);
	temp.vec.push_back(pair<int,int>(0,0));
	queue<pot>q;
	q.push(temp);
	while(!q.empty())
	{
		temp=q.front();
		q.pop();
		if(temp.a==c||temp.b==c)
		{
			output(temp.vec);
			return 0;
		}
		if(!v[temp.a][b])
		{
			v[temp.a][b]=true;
			pot p(temp);
			p.b=b;
			p.vec.push_back(pair<int,int>(2,3));
			q.push(p);
		}
		if(!v[a][temp.b])
		{
			v[a][temp.b]=true;
			pot p(temp);
			p.a=a;
			p.vec.push_back(pair<int,int>(1,3));
			q.push(p);
		}
		int aa=temp.a+temp.b,bb=0;
		if(aa>a)
		{
			bb=aa-a;
			aa=a;
		}
		if(!v[aa][bb])
		{
			v[aa][bb]=true;
			pot p(temp);
			p.a=aa,p.b=bb;
			p.vec.push_back(pair<int,int>(2,1));
			q.push(p);
		}
		aa=0,bb=temp.a+temp.b;
		if(bb>b)
		{
			aa=bb-b;
			bb=b;
		}
		if(!v[aa][bb])
		{
			v[aa][bb]=true;
			pot p(temp);
			p.a=aa,p.b=bb;
			p.vec.push_back(pair<int,int>(1,2));
			q.push(p);
		}
		if(!v[temp.a][0])
		{
			v[temp.a][0]=true;
			pot p(temp);
			p.b=0;
			p.vec.push_back(pair<int,int>(2,4));
			q.push(p);
		}
		if(!v[0][temp.b])
		{
			v[0][temp.b]=true;
			pot p(temp);
			p.a=0;
			p.vec.push_back(pair<int,int>(1,4));
			q.push(p);
		}
	}
	cout<<"impossible"<<endl;
	return 0;
}

• Re:我也留个代码,,vector水过,,,,, (2151) jianjungki 2010-12-10 20:57:51