4643250_wa.cc

部分PKU上的源码

#include<iostream>
using namespace std;
bool used[105][105];
int usedn;
struct state
{
	int pi,pj;
	int action;
} e[105][105];
struct st
{
	int i,j;
}line[10005];
int f,be;
int a,b,c;
int actionline[10005];
int actioncount;
void out(st x)
{
	actioncount=0;
	while(x.i!=-1)
	{
		int i=x.i,j=x.j;
		actionline[actioncount]=e[i][j].action;
		actioncount++;
		x.i=e[i][j].pi;
		x.j=e[i][j].pj;
	}
	cout<<actioncount-1<<endl;
	for(int count=actioncount-1;count>=0;count--)
	{
		switch(actionline[count])
		{
		case 1:cout<<"FILL(1)\n";break;
		case 2:cout<<"FILL(2)\n";break;
		case 3:cout<<"POUR(2,1)\n";break;
		case 4:cout<<"POUR(1,1)\n";break;
		case 5:cout<<"DROP(1)\n";break;
		case 6:cout<<"DROP(2)\n";break;
		}
	}
}
st justdo(int count,st x)
{
	switch(count)
	{
	case 1:x.i=a;return x;
	case 2:x.j=b;return x;
	case 3:if(x.i+x.j>a){x.j=x.i+x.j-a;x.i=a;return x;}
		else{x.i=x.i+x.j;x.j=0;return x;}
	case 4:if(x.i+x.j>b){x.i=x.i+x.j-b;x.j=b;return x;}
		else{x.j=x.i+x.j;x.i=0;return x;}
	case 5:x.i=0;return x;
	case 6:x.j=0;return x;
	}
	return x;
}
void BFS()
{
	memset(used,false,sizeof(used));
	line[0].i=0;line[0].j=0;
	e[0][0].pi=-1;e[0][0].pj=-1;
	used[0][0]=true;
	usedn=1;
	f=0;be=1;
	while(f<be)
	{
		if(line[f].i==c||line[f].j==c)
		{
			out(line[f]);return;
		}
		else 
		{
			for(int count=1;count<=6;count++)
			{
				st temp=justdo(count,line[f]);
				if(used[temp.i][temp.j]==false)
				{
					line[be]=temp;
				//	cout<<temp.i<<" "<<temp.j<<endl;
					be++;
					e[temp.i][temp.j].pi=line[f].i;
					e[temp.i][temp.j].pj=line[f].j;
					e[temp.i][temp.j].action=count;
					used[temp.i][temp.j]=true;
				}
			}
		}
		f++;
	}
	cout<<"impossible\n";
}
int main()
{
	while(scanf("%d%d%d",&a,&b,&c)!=EOF)
	{
		BFS();
	}
	return 0;
}