#include <iostream>
#include <queue>
#include <cstring>
#include <string>
using namespace std;
int A,B,C;
bool check[400][400];
string step[400][400];
int depth[200][200];
typedef struct Now
{
	int A,B;
}now;
string BFS()
{
	queue<now>l;
	now top;
	top.A=0,top.B=0;
	l.push(top);
	memset(check,false,sizeof(check));
	memset(step,0,sizeof(step));
	memset(depth,0,sizeof(depth));
	while (!l.empty())
	{
		top=l.front();
		l.pop();
		if(top.A==C || top.B==C ){ cout<<depth[top.A][top.B]<<endl; return step[top.A][top.B];}
		check[top.A][top.B]=true;
		
		now temp=top;   //fill A
		temp.A=A;
		string tt="FILL(1)\n";
		if(check[temp.A][temp.B]==false){ l.push(temp);step[temp.A][temp.B]=step[top.A][top.B]+tt;depth[temp.A][temp.B]=depth[top.A][top.B]+1;}

		temp=top; //fill B;
		temp.B=B;
		tt="FILL(2)\n";
		if(check[temp.A][temp.B]==false){ l.push(temp);step[temp.A][temp.B]=step[top.A][top.B]+tt;depth[temp.A][temp.B]=depth[top.A][top.B]+1;}

		temp=top;  //drop A
		temp.A=0;
		tt="DROP(1)\n";
		if(check[temp.A][temp.B]==false){ l.push(temp);step[temp.A][temp.B]=step[top.A][top.B]+tt;depth[temp.A][temp.B]=depth[top.A][top.B]+1;}

		temp=top;  //drop B
		temp.B=0;
		tt="DROP(2)\n";
		if(check[temp.A][temp.B]==false){ l.push(temp);step[temp.A][temp.B]=step[top.A][top.B]+tt;depth[temp.A][temp.B]=depth[top.A][top.B]+1;}

		temp=top;  //pour A to B
		if(B-top.B>=top.A)temp.A=0,temp.B+=top.A;
		else temp.A=top.A-B+top.B,temp.B=B;
		tt="POUR(1,2)\n";
		if(check[temp.A][temp.B]==false){ l.push(temp);step[temp.A][temp.B]=step[top.A][top.B]+tt;depth[temp.A][temp.B]=depth[top.A][top.B]+1;}

		temp=top;  //pour B to A
		if(A-top.A>=top.B)temp.B=0,temp.A+=top.B;
		else temp.B=top.B-A+top.A,temp.A=A;
		tt="POUR(2,1)\n";
		if(check[temp.A][temp.B]==false){ l.push(temp);step[temp.A][temp.B]=step[top.A][top.B]+tt;depth[temp.A][temp.B]=depth[top.A][top.B]+1;}
	}
	return "impossible\n";
}
int main()
{
	while(cin>>A>>B>>C) cout<<BFS();
	return 0;
}

• Re:我也来发发自己的拙代码吧 (10) buptpanda 2012-10-07 22:42:30