搜索：zoj 1005 Jugs || poj 1606 (广搜做法)
【转】http://blog.csdn.net/zxy_snow/article/details/5740824
#include <stdio.h>
#include <stdlib.h>
#define Afull 1
#define Bfull 2
#define Aempty 3
#define Bempty 4
#define AtoB 5
#define BtoA 6???????
//下面用着方便呀~
int head,tail;
char step[7][10] = {"0","fill A","fill B","empty A","empty B","pour A B","pour B A"};
struct pos???????? //算是链表吧
{
??? int mark;
??? int a;
??? int b;
??? struct pos *former;
};
typedef struct pos sta;
sta Q[100000];???????? //队列
void EnQ(sta x)??????? //入队
{
??? Q[head++] = x;
}
sta DeQ(void)?????????? //出队
{
??? return Q[tail++];
}
int check( sta x )?????? //判断是否A B 是否重复
{
??? int i;
??? for( i=0; i<head; i++)
??????? if( Q[i].a==x.a && Q[i].b==x.b)
??????????? return 1;
??? return 0;
}
int Qempty(void)??? //判断队列是否为空
{
??? if( head == tail )
??????? return 1;
??? return 0;
}
/**********************主函数**************************/
int main(void)
{
??? int A,B,N,i;
??? sta temp,*point,s,*search,*result[100000];
??? while ( scanf("%d%d%d",&A,&B,&N)!=EOF )
??? {
??????? head = 0;
??????? tail = 0;
??????? temp.a = 0;
??????? temp.b = 0;
??????? temp.mark = 0;
??????? temp.former = NULL;
??????? EnQ( temp );
??????? while( !Qempty() )
??????? {
??????????? temp = DeQ();
??????????? point = &Q[tail-1];
??????????? if( temp.a == N || temp.b == N )????
??????????????? break;
???????????????
??????????? s = temp;
??????????? s.a = A;
??????????? if( !check(s) && temp.a != A ) // Afull
??????????? {
??????????????? s.former = point;
??????????????? s.mark = Afull;
??????????????? EnQ(s);
??????????? }
???????????
??????????? s = temp;
??????????? s.b = B;
??????????? if( !check(s) && temp.b != B )? //Bfull
??????????? {
??????????????? s.former = point;
??????????????? s.mark = Bfull;
??????????????? EnQ(s);
??????????? }
???????????
??????????? s = temp;
??????????? s.a = 0;
??????????? if( !check(s) && temp.a )? //Aempty
??????????? {
??????????????? s.former = point;
??????????????? s.mark = Aempty;
??????????????? EnQ(s);
??????????? }
???????????
??????????? s = temp;
??????????? s.b = 0;
??????????? if( !check(s) && temp.b )? //Bempty
??????????? {
??????????????? s.former = point;
??????????????? s.mark = Bempty;
??????????????? EnQ(s);
??????????? }
???????????
??????????? s = temp;
??????????? if( s.a!=0 && s.b<B && s.a<= B- s.b ) // AtoB
??????????? {
??????????????? s.b += s.a;
??????????????? s.a = 0;
??????????????? if( !check(s) )
??????????????? {
??????????????????? s.former = point;
??????????????????? s.mark = AtoB;
??????????????????? EnQ(s);
??????????????? }
??????????? }
??????????? else
??????????? {
??????????????? if( s.a!=0 && s.b<B)
??????????????? {
??????????????????? s.a -= (B - s.b);
??????????????????? s.b = B;
??????????????????? if( !check(s) )
??????????????????? {
??????????????????????? s.former = point;
??????????????????????? s.mark = AtoB;
??????????????????????? EnQ(s);
??????????????????? }
??????????????? }
??????????? }
??????????? s = temp;
??????????? if( s.b!=0 && s.a<A && s.b<= A- s.a ) //BtoA
??????????? {
??????????????? s.a += s.b;
??????????????? s.b = 0;
??????????????? if( !check(s) )
??????????????? {
??????????????????? s.former = point;
??????????????????? s.mark = BtoA;
??????????????????? EnQ(s);
??????????????? }
??????????? }
??????????? else
??????????? {
??????????????? if( s.b!=0 && s.a<A)
??????????????? {
??????????????????? s.b -= (A - s.a);
??????????????????? s.a = A;
??????????????????? if( !check(s) )
??????????????????? {
??????????????????????? s.former = point;
??????????????????????? s.mark = BtoA;
??????????????????????? EnQ(s);
??????????????????? }
??????????????? }
??????????? }
??????? }
??????? search = point;
??????? for(i=0; search!=NULL;i++)?? //查找到第一个节点
??????? {
??????????? result[i] = search;
??????????? search = search->former;
??????? }
??????? for(i-=2; i>=0; i--)
??????????? puts( step[result[i]->mark] );
??????? printf("success/n");
??? }
system("pause");
return 0;
}
