Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

贴个代码

Posted by shine_ at 2014-08-08 17:08:46 on Problem 3414
#include<stdio.h>
#include<cstring>
#include<iostream>
#include<cstring>
using namespace std;
struct State
{
    int post;
    int a,b;
    int step;
    char d[10];
}state[10010];
int haha[10010];
int A,B,C;
bool visit[105][105];//标记该状态时否被访问过
int BFS()
{
    int head=0,tail=0;
    visit[0][0]=true;
    state[tail].a=0;
    state[tail].b=0;
    state[tail].step=0;
    state[tail].post=-2;
    tail++;
    while(1)
    {
        State x=state[head];
        //cout<<state[head].a<<"*"<<state[head].b<<endl;
        if(head==tail)
        {
           return -1;//队列为空,找不到.
        }

        if(x.a==C||x.b==C)
        {
            return head;
        }

        if(!visit[A][x.b])// fill A;
        {
            visit[A][x.b]=true;
            state[tail].b=x.b;
            state[tail].a=A;
            state[tail].post=head;
            strcpy(state[tail].d,"FILL(1)");
            state[tail++].step=x.step+1;
        }
        if(!visit[x.a][B]) //fill B
        {
            visit[x.a][B]=true;
            state[tail].a=x.a;
            state[tail].b=B;
            state[tail].post=head;
            strcpy(state[tail].d,"FILL(2)");
            state[tail++].step=x.step+1;
        }


        if(x.a+x.b<=B)    //pour(a,b)
        {
            if(!visit[0][x.a+x.b])
            {
                visit[0][x.a+x.b]=true;
                state[tail].b=x.a+x.b;
                state[tail].a=0;
                state[tail].post=head;
                strcpy(state[tail].d,"POUR(1,2)");
                state[tail++].step=x.step+1;
            }
        }
        else
        {
            if(!visit[x.a-(B-x.b)][B])
            {
                visit[x.a-(B-x.b)][B]=true;
                state[tail].a=x.a-(B-x.b);
                state[tail].b=B;
                state[tail].post=head;
                strcpy(state[tail].d,"POUR(1,2)");
                state[tail++].step=x.step+1;
            }
        }

        if(x.b+x.a<=A)   //pour(b,a);
        {
            if(!visit[x.a+x.b][0])
            {
                visit[x.a+x.b][0]=true;
                state[tail].a=x.a+x.b;
                state[tail].step=x.step+1;
                state[tail].post=head;
                strcpy(state[tail].d,"POUR(2,1)");
                state[tail++].b=0;
            }
        }
        else
        {
            if(!visit[A][x.b-(A-x.a)])
            {
                visit[A][x.b-(A-x.a)]=true;
                state[tail].b=x.b-(A-x.a);
                state[tail].a=A;
                state[tail].post=head;
                strcpy(state[tail].d,"POUR(2,1)");
                state[tail++].step=x.step+1;
            }
        }

         if(!visit[0][x.b]) //drop A
        {
            visit[0][x.b]=true;
            state[tail].a=0;
            state[tail].b=x.b;
            state[tail].post=head;
            strcpy(state[tail].d,"DROP(1)");
            state[tail++].step=x.step+1;
        }
        if(!visit[x.a][0]) //drop B
        {
            visit[x.a][0]=true;
            state[tail].b=0;
            state[tail].a=x.a;
            state[tail].post=head;
            strcpy(state[tail].d,"DROP(2)");
            state[tail++].step=x.step+1;
        }
        head++;
    }
}
int main()
{
    while(scanf("%d%d%d",&A,&B,&C)!=EOF)
    {
        memset(visit,false,sizeof(visit));
        int t=BFS();
        if(t==-1)
        printf("impossible\n");
        else
        {
            int i=0;
            while(state[t].post!=-2)
            {

                haha[i]=t;
                i++;
                t=state[t].post;
            }
            cout<<i<<endl;
            for(int j=i-1;j>=0;j--)
            {
                cout<<state[haha[j]].d<<endl;
            }
        }
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator