搜寻：zoj 1005 Jugs || poj 1606 (广搜做法)

搜索：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;
}