Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
贴个代码#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator