poj 3414 Pots

17365 단어 poj
http://poj.org/problem?id=3414


while(scanf("%d%d%d",&A,&B,&C)!=EOF)
Output Limit Exceeded
#include
<iostream> #include<string> #include<string.h> #include<queue> #include<stdio.h> #include<map> using namespace std; const int N=100001; int go[6]={-1,-2,-3,1,2,3}; int a[N]; int b[N]; int pre[N]; int type[N]; bool had[105][105]; int I,K,J; int anstype[N]; int ans,nd; int A,B,C; bool ok(int a1,int b1,int i) { //cout<<a1<<" "<<b1<<" "<<i<<endl; int l1,l2; if(i==-1) { l1=A;l2=b1; }else if(i==-2) { l1=0;l2=b1; }else if(i==-3) { l1=min(A,a1+b1);l2=max(0,a1+b1-A); }else if(i==1) { l1=a1;l2=B; }else if(i==2) { l1=a1;l2=0; }else { l2=min(B,a1+b1);l1=max(0,a1+b1-B); } if(had[l1][l2]) return false; had[l1][l2]=true; type[J]=i; pre[J]=I; //cout<<l1<<" "<<l2<<endl; a[J]=l1;b[J]=l2;++J; if(l1==C||l2==C) return true; return false; } void bfs(int k) {//cout<<k<<endl; if(K==J) return; K=J; for(;I<K;++I) { for(int i=0;i<6;++i) if(ok(a[I],b[I],go[i])) { ans=k;nd=J-1; return; } } bfs(k+1); } void print() { int i=ans; int l=nd; while(l!=0) { anstype[i]=type[l]; l=pre[l]; --i; } for(i=1;i<=ans;++i) { if(anstype[i]==-1) printf("FILL(1)
"); if(anstype[i]==-2) printf("DROP(1)
"); if(anstype[i]==-3) printf("POUR(2,1)
"); if(anstype[i]==1) printf("FILL(2)
"); if(anstype[i]==2) printf("DROP(2)
"); if(anstype[i]==3) printf("POUR(1,2)
"); } } int main() { scanf("%d%d%d",&A,&B,&C); memset(had,false,sizeof(had)); had[0][0]=true; a[0]=0;b[0]=0; pre[0]=0; type[0]=0; I=K=0;J=1; ans=-1; bfs(1); if(ans==-1) { printf("impossible
"); } else { printf("%d
",ans); print(); } return 0; }

좋은 웹페이지 즐겨찾기