G - Pots（罐子）——POJ bfs搜索

Pots

题意：给你两个罐子A和B，你可以进行六种操作，让你求得最少的步骤使得A或B的罐子容量为C。

解题思路：A和B都在动态变化，我们可以将他们关联起来，利用结构体数组记录当前状态和步骤数，同样，我们要利用辅助数组visited来判断当前状态是否被访问。这里最难的就是记录步骤，然后输出每轮步骤，由于我们要按照原序输出，故我们可以利用栈来实现步骤输出。则此题可解。

AC代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<stack>
#include<queue>
#include<memory.h>

using namespace std;

const int maxn=105;
int a,b,c;
typedef struct node1  //a代表罐1，b代表罐2，其中step代表操作步骤数。
{
	int a;
	int b;
	int step;
}node1;
typedef struct node2
{
	int i;//记录操作
	node2 *pre;//记录前驱结点。
}node2;
bool visited[maxn][maxn]; //标志数组，避免重复进行步骤，到死循环。

void print(int n)
{
	if(n==0)cout<<"FILL(1)"<<endl;
	else if(n==1)cout<<"DROP(1)"<<endl;
	else if(n==2)cout<<"POUR(1,2)"<<endl;
	else if(n==3)cout<<"FILL(2)"<<endl;
	else if(n==4)cout<<"DROP(2)"<<endl;
	else cout<<"POUR(2,1)"<<endl;
}
int bfs(int a,int b,int c,node2 *p)
{
	queue<node1>  Q;
	node1 head,temp;
	head.a=head.b=head.step=0;
	visited[head.a][head.b]=true;
	Q.push(head);
	int s=0;int pre_s=-1;p[s].pre=NULL;int i;
	while(!Q.empty())
	{
		head=Q.front();
		Q.pop();
		pre_s++;
		for(i=0;i<6;i++)
		{
			temp.a=head.a;temp.b=head.b;temp.step=head.step;
			if(i==0)
			{
				temp.a=a;
			}
			else if(i==1)
			{
				temp.a=0;
			}
			else if(i==2)
			{
				if(temp.a>=b-temp.b)
				{
					temp.a=temp.a-b+temp.b;
					temp.b=b;
				}
				else
				{
					temp.b+=temp.a;
					temp.a=0;
				}
			}
			else if(i==3)
			{
				temp.b=b;
			}
			else if(i==4)
			{
				temp.b=0;
			}
			else if(i==5)
			{
				if(temp.b>=a-temp.a)
				{
					temp.b=temp.b-a+temp.a;
					temp.a=a;
				}
				else
				{
					temp.a+=temp.b;
					temp.b=0;
				}
			}
		if(!visited[temp.a][temp.b])
		{
			s++;
			p[s].i=i;
			p[s].pre=&p[pre_s];//指向前驱结点。两者都在更新。
			visited[temp.a][temp.b]=true;   //改标志
			temp.step+=1;                    //记录步骤
			Q.push(temp);                    //入队
			if(temp.a==c||temp.b==c)         //已匹配，接下来就是压栈
			{
				cout<<temp.step<<endl;
				stack<node2> S;
				node2 x=p[s];
				while(x.pre!=NULL)
				{
					S.push(x);
					x=*(x.pre);
				}
				while(!S.empty())
				{
					x=S.top();
					S.pop();
					print(x.i);
				}
				return 0;
			}
		}
		}
	}
	cout<<"impossible"<<endl;
	return 0;
}
int main()
{
	while(cin>>a>>b>>c)
	{
		node2 p[10005];
		memset(visited,false,sizeof(visited));
		bfs(a,b,c,p);
	}
}