poj3414——Pots

绝对的BFS好题！在实验室师兄的启发下，1A！

代码有点长...

#include<stdio.h>
#include<string.h>
struct node
{
	int u1,u2,step;
}tt[10000];
bool vis[105][105];
int a,b,c,front=0,rear=0;
int pre[10000];
void pri(int front)
{
	int i,top=1,s,x,y;
	struct node kk[1000];
	kk[top]=tt[front];
	s=pre[front];
	while(s!=-1)
	{
		kk[++top]=tt[s];
		s=pre[s];
	}
	printf("%d\n",top-1);
	for(i=top-1;i>0;i--)
	{
		int k=kk[i].step ;
		switch(k){
	case 1:
		printf("FILL(1)\n");
		break;
	case 2:
		printf("DROP(1)\n");
		break;
	case 3:
		printf("POUR(1,2)\n");
		break;
	case 4:
		printf("FILL(2)\n");
		break;
	case 5:
		printf("DROP(2)\n");
		break;
	default :
		printf("POUR(2,1)\n");
		break;
		}
	}
}
void solve()
{
	int i,tempx,tempy,x,y;
	bool flag=true;
	memset(pre,-1,sizeof(pre));
	scanf("%d%d%d",&a,&b,&c);
	rear++;
	tt[rear].u1=0;tt[rear].u2=0;tt[rear].step =-1;
	memset(vis,true,sizeof(vis));
	vis[0][0]=false;
	while(rear!=front)
	{
		front++;x=tt[front].u1;y=tt[front].u2;
		if(x+y==c||x==c||y==c)
		{
			pri(front);
			flag=false;
			break;
		}
		for(i=1;i<=6;i++)
		{
			switch(i)
			{
			case 1:
				if(x<a)
				{
					tempx=a;tempy=y;
					if(vis[tempx][tempy])
					{
						vis[tempx][tempy]=false;
						tt[++rear].u1=tempx;tt[rear].u2=tempy;tt[rear].step =i;
						pre[rear]=front;
					}
				}
				break;
			case 2:
				if(x>0)
				{
					tempx=0;tempy=y;
					if(vis[tempx][tempy])
					{
						vis[tempx][tempy]=false;
						tt[++rear].u1=tempx;tt[rear].u2=tempy;tt[rear].step =i;
						pre[rear]=front;
					}
				}
				break;
			case 3:
				if(x>0&&y<b)
				{
					if(b-y>=x)
					{
						tempx=0;tempy=y+x;
						if(vis[tempx][tempy])
						{
							vis[tempx][tempy]=false;
							tt[++rear].u1=tempx;tt[rear].u2=tempy;tt[rear].step =i;
							pre[rear]=front;
						}
					}
					else 
					{
						tempx=x-(b-y);tempy=b;
						if(vis[tempx][tempy])
						{
							vis[tempx][tempy]=false;
							tt[++rear].u1=tempx;tt[rear].u2=tempy;tt[rear].step =i;
							pre[rear]=front;
						}
					}
				}
				break;
			case 4:
				if(y<b)
				{
					tempx=x;tempy=b;
					if(vis[tempx][tempy])
					{
						vis[tempx][tempy]=false;
						tt[++rear].u1=tempx;tt[rear].u2=tempy;tt[rear].step =i;
						pre[rear]=front;
					}
				}
				break;
			case 5:
				if(y>0)
				{
					tempx=x;tempy=0;
					if(vis[tempx][tempy])
					{
						vis[tempx][tempy]=false;
						tt[++rear].u1=tempx;tt[rear].u2=tempy;tt[rear].step =i;
						pre[rear]=front;
					}
				}
				break;
			default :
				if(y>0&&x<a)
				{
					if(a-x>=y)
					{
						tempx=x+y;tempy=0;
						if(vis[tempx][tempy])
						{
							vis[tempx][tempy]=false;
							tt[++rear].u1=tempx;tt[rear].u2=tempy;tt[rear].step =6;
							pre[rear]=front;
						}
					}
					else 
					{
						tempx=a;tempy=y-(a-x);
						if(vis[tempx][tempy])
						{
							vis[tempx][tempy]=false;
							tt[++rear].u1=tempx;tt[rear].u2=tempy;tt[rear].step =6;
							pre[rear]=front;
						}
					}
				}
				break;
			}
		}
	}
	if(flag)
		printf("impossible\n");
}
int main()
{
	solve();
	return 0;
}