TIOJ 1008 量杯問題

[BFS]
原來叫做"隱式圖搜索"@@

#include<algorithm>
#include<cmath>
#include<stdio.h>
#include<cstdlib>
#include<queue>
#include<set>
#include<cstring>
using namespace std;
#define min(x,y) (((x)>(y)) ? (y):(x))
#define max(x,y) (((x)>(y)) ? (x):(y))
#define LL long long int
class State
{
public:
    LL I[5];
    int Step;
    State(){I[0]=I[1]=I[2]=I[3]=I[4]=0,Step=0;}
    LL GetNum()const
    {return I[0]+I[1]*51+I[2]*51*51+I[3]*51*51*51+I[4]*51*51*51*51;}
    void Print(){printf("(%I64d %I64d %I64d %I64d %I64d)STP=%d\n",I[0],I[1],I[2],I[3],I[4],Step);}
};
queue<State> BFS;
set<LL> TB;
void Test(State IS)
{
    if(TB.count(IS.GetNum())) return;
    BFS.push(IS);
    TB.insert(IS.GetNum());
}
int main()
{
    TB.clear();
    int T;          scanf("%d",&T);
    LL Cont[5]; for(int lx=0;lx<T;lx++) scanf("%I64d",&Cont[lx]);
    LL Target;      scanf("%I64d",&Target);

    LL G=0;LL MAX=0;
    for(int lx=0;lx<T;lx++)
        G=__gcd(G,Cont[lx]);
    if(Target%G)
    {
        printf("-1\n");
        return 0;
    }
    for(int lx=0;lx<T;lx++)
        MAX=max(Cont[lx],MAX);
    if(MAX<Target)
    {
        printf("-1\n");
        return 0;
    }
    State Start;BFS.push(Start);
    bool OK=false;
    while(BFS.size()&&(OK==false))
    {
        State TMP=BFS.front();
        //TMP.Print();
        if((TMP.I[0]==Target)||(TMP.I[1]==Target)||(TMP.I[2]==Target)||
            (TMP.I[3]==Target)||(TMP.I[4]==Target))
            break;
        BFS.pop();
        for(int lx=0;lx<T;lx++)
        {
            State SA=TMP;SA.Step++;
            if(SA.I[lx]>0)
            {
                SA.I[lx]=0;
                Test(SA);
            }
            if(SA.I[lx]<Cont[lx])
            {
                SA.I[lx]=Cont[lx];
                Test(SA);
            }
            for(int ly=0;ly<T;ly++)
            {
                if(TMP.I[lx]==0) break;
                SA=TMP;
                SA.Step++;
                if(lx==ly) continue;
                LL Last=Cont[ly]-SA.I[ly];
                LL mm=min(Last,SA.I[lx]);
                SA.I[ly]+=mm,SA.I[lx]-=mm;
                Test(SA);
            }
        }
    }
    printf("%d\n",BFS.front().Step);
    return 0;
}