//一不小心AC了...这道题目挺好玩的哈  BFS
//2个瓶子倒水，一共有6种倒法，枚举即可，但相同出现的状态不要重复出现
//并且还要记住上一次的操作。。。
//因为是special judge，所以我觉得DFS也可以吧?

#include<iostream>
using namespace std;

bool visit[110][110];//标记某种状态是否已经出现过

struct node
{
	int x;//A瓶的剩余量
	int y;//B瓶的剩余量
	int pre;//上一次操作的ID值
	int step;//走到这一步时候的步骤数目
	int op;//操作的类型：从1到6

};

node q[100000],temp,tt;//队列



int rear,front,x,y,step,ID,xx,yy;
int m,n,rest;

void show(int pre)//递归输出结果
{
	if(pre==-1)//直接返回，不必输出
		return ;
	show(q[pre].pre);

	if(q[pre].op==1)
	{
		printf("FILL(1)\n");
		return ;
	}

	if(q[pre].op==2)
	{
		printf("FILL(2)\n");
		return ;
	}

	if(q[pre].op==3)
	{
		printf("DROP(1)\n");
		return ;
	}

	if(q[pre].op==4)
	{
		printf("DROP(2)\n");
		return ;
	}

	if(q[pre].op==5)
	{
		printf("POUR(1,2)\n");
		return ;
	}

	if(q[pre].op==6)
	{
		printf("POUR(2,1)\n");
		return ;
	}
}

void process()//BFS函数
{
	int i;
	visit[0][0]=1;

	temp.pre=-1;
	temp.step=0;
	temp.x=0;
	temp.y=0;

	q[rear++]=temp;//初始化

	while(front!=rear)//队列为空，退出
	{
		tt=q[front++];

		x=tt.x;
		step=tt.step;
		y=tt.y;

		if(x==rest||y==rest)//找到一个最快的结果
		{
			printf("%d\n",step);
			show(front-1);
			return ;
		}

		for(i=1;i<=6;i++)
		{
			if(i==1)
			{
				xx=m;
				yy=y;
				
				if(!visit[xx][yy])
				{
					q[rear].x=xx;
					q[rear].y=yy;
					q[rear].op=i;
					q[rear].step=step+1;
					q[rear++].pre=front-1;
					visit[xx][yy]=1;

				}
				
				continue;
			}

			if(i==2)
			{
				xx=x;
				yy=n;
				
				if(!visit[xx][yy])
				{
					q[rear].x=xx;
					q[rear].y=yy;
					q[rear].op=i;
					q[rear].step=step+1;
					q[rear++].pre=front-1;
					visit[xx][yy]=1;

				}
				
				continue;
			}

			if(i==3)
			{
				xx=0;
				yy=y;
				
				if(!visit[xx][yy])
				{
					q[rear].x=xx;
					q[rear].y=yy;
					q[rear].op=i;
					q[rear].step=step+1;
					q[rear++].pre=front-1;
					visit[xx][yy]=1;

				}
				
				continue;
			}

			if(i==4)
			{
				xx=x;
				yy=0;
				
				if(!visit[xx][yy])
				{
					q[rear].x=xx;
					q[rear].y=yy;
					q[rear].op=i;
					q[rear].step=step+1;
					q[rear++].pre=front-1;
					visit[xx][yy]=1;

				}
				
				continue;
			}

			if(i==5)
			{
				if(x>n-y)
				{
					xx=x-n+y;
					yy=n;
				}
				else
				{
					xx=0;
					yy=y+x;
				}
				
				if(!visit[xx][yy])
				{
					q[rear].x=xx;
					q[rear].y=yy;
					q[rear].op=i;
					q[rear].step=step+1;
					q[rear++].pre=front-1;
					visit[xx][yy]=1;

				}
				
				continue;
			}

			if(i==6)
			{
				if(y>m-x)
				{
					xx=m;
					yy=y-m+x;
				}
				else
				{
					xx=x+y;
					yy=0;
				}
				
				if(!visit[xx][yy])
				{
					q[rear].x=xx;
					q[rear].y=yy;
					q[rear].op=i;
					q[rear].step=step+1;
					q[rear++].pre=front-1;
					visit[xx][yy]=1;

				}
				
				continue;
			}


		}

	}
	printf("impossible\n");
	

}
int main()
{
	scanf("%d%d%d",&m,&n,&rest);
	process();
	return 0;
}

• Re:幼稚代码献上(BFS) (2) xiaoz013 2010-08-26 16:50:22