> #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;
> 
> }

• Re:代码很赞，学习了~ (9) CJQ2011 2012-09-20 11:32:27