广度优先搜索BFS（简单）

    都做过倒水的问题，有一个3升和5升的水桶和无限的水，现在要求桶中恰好装入4升水。POJ3414就是这类的倒水问题，给你两个桶，容量为A,B。现在要求称出C升水。（1<=A,B<=100，C<=MAX(A,B)）

    并且要使操作次数最少，打印最少次数和操作。

    操作次数最少，显然是广度优先搜索可以快速达到要求。对于两个桶的状态，它一共有六种操作：把A倒满，把B倒满，把A清空，把B清空，把A中的水倒入B，把B中的水倒入A。这样搜索就是搜索一棵6叉树，注意保存路径（每个状态都有一个父状态）。

 

#include <iostream>
using namespace std;

const int MAX = 100000;
short A,B,C;
int length;
bool flag[101][101];

typedef struct 
{
	short a;
	short b;
	short op;	//op = 1,倒满s；op=2，清空s；op=3，把s到入e
	short s;
	short e;
	int parent;
}Condition;
Condition queue[MAX];

int k = -1;

void print(int p)
{
	if(p != -1)
	{
		k++;
		print(queue[p].parent);
	}
	if(p == -1)
	{
		printf("%d\n",k);
		return;
	}
	if(queue[p].op == 1)
		printf("FILL(%d)\n", queue[p].s);
	if(queue[p].op == 2)
		printf("DROP(%d)\n", queue[p].s);
	if(queue[p].op == 3)
		printf("POUR(%d,%d)\n", queue[p].s, queue[p].e);
}

int main()
{
	int i,j;
	short a,b;
	bool tag = false;
	Condition now;
	memset(flag,0,sizeof(flag));
	cin>>A>>B>>C;
	Condition initial;
	initial.a = 0;
	initial.b = 0;
	initial.op = -1;
	initial.parent = -1;
	flag[0][0] = true;
	queue[0] = initial;
	int head = 0,tail = 1;
	while(head != tail)
	{
		now = queue[head++];
		a = now.a; b = now.b;
		if(now.a == C || now.b == C)
		{
			tag = true;
			break;
		}
		//6种操作:把1填满，把2填满，把1倒空，把2倒空，把1的水倒入2，把2的水到入1
		Condition adj1;
		adj1.a = A;
		adj1.b = b;
		if(!flag[A][b])
		{
			adj1.parent = head - 1;
			adj1.op = 1;
			adj1.s = 1;
			queue[tail++] = adj1;
			flag[A][b] = true;
		}
		adj1.a = a;
		adj1.b = B;
		if(!flag[a][B])
		{
			adj1.parent = head - 1;
			adj1.op = 1;
			adj1.s = 2;
			queue[tail++] = adj1;
			flag[a][B] = true;
		}
		adj1.a = 0;
		adj1.b = b;
		if(!flag[0][b])
		{
			adj1.parent = head - 1;
			adj1.op = 2;
			adj1.s = 1;
			queue[tail++] = adj1;
			flag[0][b] = true;
		}
		adj1.a = a;
		adj1.b = 0;
		if(!flag[a][0])
		{
			adj1.parent = head - 1;
			adj1.op = 2;
			adj1.s = 2;
			queue[tail++] = adj1;
			flag[a][0] = true;
		}
		adj1.a = a + b - B;
		if(adj1.a < 0)
		{
			adj1.a = 0;
			adj1.b = a + b;
		}
		else
		{
			adj1.b = B;
		}
		if(!flag[adj1.a][adj1.b])
		{
			adj1.parent = head - 1;
			adj1.op = 3;
			adj1.s = 1;
			adj1.e = 2;
			queue[tail++] = adj1;
			flag[adj1.a][adj1.b] = true;
		}
		adj1.b = a + b - A;
		if(adj1.b < 0)
		{
			adj1.b = 0;
			adj1.a = a + b;
		}
		else
		{
			adj1.a = A;
		}
		if(!flag[adj1.a][adj1.b])
		{
			adj1.parent = head - 1;
			adj1.op = 3;
			adj1.s = 2;
			adj1.e = 1;
			queue[tail++] = adj1;
			flag[adj1.a][adj1.b] = true;
		}
	}
	if(tag)
		print(head - 1);
	else
		cout<<"impossible\n";
	return 0;
}

    参见POJ3414