唉，承认写的东西是恶心了点，走过路过的牛们就帮忙看看怎么ac不了吧，测试数据都是对的，自己出的数据也是对的。。。。。。是poj的错还是我的错？？？代码有点长，见谅。

//poj 3414 pots

#include<iostream>
#include<queue>
#include<memory.h>
const int MAX = 101;
const int MAX2 = 20000;
using namespace std;

struct node
{
	int pot1;
	int pot2;
	int Id;
	node(int p1 = 0, int p2 = 0,int i = 0):pot1(p1),pot2(p2),Id(i){ }
};

char opt[6][12] = {"FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"};
bool map[MAX][MAX];       //判重
bool flag = false;
int proc[MAX2][2];         //记录过程,[i][0] is method, [i][1] is father_id;
int procId;                //搜索过节点的ID
int a, b, c;
int num;

int print(int id)                   //递归输出方案
{
	if(proc[id][1] != -1)
	{
	num++;
	print(proc[id][1]);
	cout<<opt[proc[id][0]]<<endl;
	}
	else cout<<num<<endl;         //输出操作数
	return 0;
}
int BFS(int x, int y)
{
	queue<struct node> q;
	q.push(node(x,y,0));
	proc[procId][0] = 0;
	proc[procId++][1] = -1;
	map[x][y] = true;
	while(!q.empty())
	{
		struct node present = q.front();
		q.pop();

		if(present.pot1 == c || present.pot2 == c )   //we find it;
		{
			flag = true;
			return 0;
		}
		int presentId = present.Id;
		if(present.pot1 != a && !map[a][present.pot2])   //fill pot1
		{
			q.push(node(a,present.pot2,procId));
			map[a][present.pot2] = true;
			proc[procId][0] = 0;
			proc[procId++][1] = presentId;
		}
		if(present.pot2 != b && !map[present.pot1][b])
		{
			q.push(node(present.pot1, b,procId));
			map[present.pot1][b] = true;
			proc[procId][0] = 1;
			proc[procId++][1] = presentId;
		}
		if(present.pot1 != 0 && !map[0][present.pot2])         //drop pot1;
		{
			q.push(node(0,present.pot2,procId));
			map[0][present.pot2] = true;
			proc[procId][0] = 2;
			proc[procId++][1] = presentId;
		}
		if(present.pot2 != 0 && !map[present.pot1][0])          //drop pot2
		{
			q.push(node(present.pot1,0,procId));
			map[present.pot1][0] = true;
			proc[procId][0] = 3;
			proc[procId++][1] = presentId;
		}

		if(present.pot1 != 0 )                            //pour i to j
		{
			if((present.pot1 - (b-present.pot2) >= 0) && !map[present.pot1 -(b-present.pot2)][b])
			{
				q.push(node(present.pot1 -(b-present.pot2), b, procId));
				map[present.pot1 -(b-present.pot2)][b] = true;
				proc[procId][0] = 4;
				proc[procId++][1] = presentId;
			}
			else if(present.pot1 - (b-present.pot2) < 0 && !map[0][present.pot1+present.pot2])
			{
				q.push(node(0,present.pot1+present.pot2,procId));
				map[0][present.pot1+present.pot2] = true;
				proc[procId][0] = 4;
				proc[procId++][1] = presentId;
			}
		}
		if(present.pot2 != 0)
		{
			if((present.pot2 - (a-present.pot1) >= 0) && !map[a][present.pot2 -(a-present.pot1)])
                        {
                                q.push(node(a,present.pot2 -(a-present.pot1), procId));
                                map[a][present.pot2 -(a-present.pot1)] = true;
                                proc[procId][0] = 5;
                                proc[procId++][1] = presentId;
                        }
                        else if((present.pot2 - (a-present.pot1) < 0) && !map[present.pot2 + present.pot1][0])
                        {
                                q.push(node(present.pot1+present.pot2, 0, procId));
                                map[present.pot1+present.pot2][0] = true;
                                proc[procId][0] = 5;
                                proc[procId++][1] = presentId;
                        }
		}
	}
	return 0;
}

int main()
{
	while(cin>>a>>b>>c)
	{
		memset(map, false, sizeof(map));
		memset(proc, -1, sizeof(proc));
		procId = 0;
		flag = false;
		num = 0;
		BFS(0,0);
//		for(int i = 0; i <= procId; i++) cout<<proc[i][0]<<' '<<proc[i][1]<<' ';   //查看过程
		if(flag)
		{
		print(procId-2);   //前面多一个，后面多一个。
		}
		else cout<<"impossible"<<endl;
	}
	return 0;	
}

• 急寻大牛阿 (0) posa88 2010-05-27 14:22:31