#include<iostream>
#include<stack>
#include<queue>
using namespace std;
struct cup
{
	int x,y;
	int step;
	int flag;
	cup * pre;
};
queue<cup> Q;
stack<int> T;
int a,b,z;
int visited[101][101]={0};
int result;
void BFS(int x,int y)
{
	visited[x][y] = 1;
	cup c;
	c.x=0;
	c.y=0;
	c.flag = 0;
	c.pre = NULL;
	c.step = 0;
	Q.push(c);
	cup temp[300];
	int count=-1;
	while(!Q.empty())
	{
		count++;
		temp[count] = Q.front();
		Q.pop();
		for(int i=1;i<=6;i++)
		{
			
			switch(i)
			{
				case 1:
					c.x = a;				//fill a
					c.y = temp[count].y;
					c.flag = 1;
					break;
				case 2:						//fill b
					c.x = temp[count].x;
					c.y = b;
					c.flag = 2;
					break;
				case 3:						//drop a
					c.x = 0;
					c.y = temp[count].y;
					c.flag = 3;
					break;
				case 4:						//drop b
					c.x = temp[count].x;
					c.y = 0;
					c.flag = 4;
					break;
				case 5:						//pour a to b
					if(temp[count].x>b-temp[count].y)
					{
						c.x = temp[count].x -(b-temp[count].y);
						c.y = b;
					}
					else 
					{
						c.x = 0;
						c.y = temp[count].y+temp[count].x;
					}
					c.flag = 5;
					break;
				case 6:						//pour b to a
					if(temp[count].y > a- temp[count].x)
					{
						c.y = temp[count].y - (a-temp[count].x);
						c.x = a;
					}
					else
					{
						c.x =temp[count].y + temp[count].x;
						c.y = 0;
					}
					c.flag = 6;
					break;
			}
			if(visited[c.x][c.y])
				continue;
			visited[c.x][c.y] = 1;
			c.step = temp[count].step + 1;		
			c.pre = &temp[count];
			
			if(c.x==z||c.y == z)
			{
				result = c.step;
				while(c.pre)
				{
					T.push(c.flag);
					c = *c.pre;
				}
				
				return;

			}
			Q.push(c);
			

		}

	}

}
int main()
{

	cin>>a>>b>>z;
	BFS(0,0);
	if(result == 0)
		cout<<"impossible"<<endl;
	else
	{
		cout<<result<<endl;
		while(!T.empty()){
			int i = T.top();
			T.pop();
			switch(i)
			{
				case 1:cout<<"FILL(1)"<<endl;break;
				case 2:cout<<"FILL(2)"<<endl;break;
				case 3:cout<<"DROP(1)"<<endl;break;
				case 4:cout<<"DROP(2)"<<endl;break;
				case 5:cout<<"POUR(1,2)"<<endl;break;
				case 6:cout<<"POUR(2,1)"<<endl;break;

			}


		}
	}
	return 0;

}

• 代码很赞，学习了~ (2563) youknow 2010-09-23 20:33:12
  • Re:代码很赞，学习了~ (9) CJQ2011 2012-09-20 11:32:27
• Re: (7) wunianqing 2014-04-11 09:26:04