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 |
写了很久1A,贴码留念#include <iostream> #include <queue> #include <algorithm> using namespace std; int rear; bool vis[110][110]; int A,B,C; struct node { int type; int num; int par; int step; int a,b; }op[1001]; queue<node> que; bool bfs() { node q; op[1].step=1,op[1].par=-1; op[2].step=1,op[2].par=-1; op[1].type=1,op[1].a=A,op[1].num=1,que.push(op[1]); op[2].type=2,op[2].b=B,op[2].num=2,que.push(op[2]); rear=2; while(!que.empty()){ node p=que.front(); if(p.a==C || p.b==C) return true; que.pop(); int temp; for(int i=1;i<=6;++i){ if(i==1 || i==2){ ++rear; op[rear].num=rear; op[rear].a=p.a,op[rear].b=p.b; op[rear].par=p.num; op[rear].type=i; op[rear].step=p.step+1; if(i==1) op[rear].a=A; else op[rear].b=B; if(!vis[op[rear].a][op[rear].b]) { que.push(op[rear]); vis[op[rear].a][op[rear].b] = true; } } if(i==3 || i==4){ ++rear; op[rear].num=rear; op[rear].a=p.a,op[rear].b=p.b; op[rear].par=p.num; op[rear].type=i; op[rear].step=p.step+1; if(i==3) op[rear].a=0; else op[rear].b=0; if(!vis[op[rear].a][op[rear].b]) { que.push(op[rear]); vis[op[rear].a][op[rear].b] = true; } } if(i==5 || i==6){ ++rear; op[rear].num=rear; op[rear].a=p.a,op[rear].b=p.b; op[rear].par=p.num; op[rear].type=i; op[rear].step=p.step+1; if(i==5 && p.a>=B-p.b){ temp=B-p.b; op[rear].a-=temp; op[rear].b=B; } else if(i==5 && p.a<B-p.b){ op[rear].a=0; op[rear].b=p.b+p.a; } else if(i==6 && p.b>=A-p.a){ temp=A-p.a; op[rear].b-=temp; op[rear].a=A; } else{ op[rear].b=0; op[rear].a=p.b+p.a; } if(!vis[op[rear].a][op[rear].b]) { que.push(op[rear]); vis[op[rear].a][op[rear].b] = true; } } } } return false; } int main() { while(~scanf("%d%d%d",&A,&B,&C)){ if(bfs()){ node ans=que.front(); vector<node> toput; for(int i=ans.num;i!=-1;i=op[i].par) { toput.push_back(op[i]); } reverse(toput.begin(),toput.end()); vector<node>::iterator iter; printf("%d\n",ans.step); for(iter=toput.begin();iter!=toput.end();++iter){ switch((*iter).type){ case 1: { puts("FILL(1)"); break; } case 2: { puts("FILL(2)"); break; } case 3: { puts("DROP(1)"); break; } case 4:{ puts("DROP(2)"); break; } case 5:{ puts("POUR(1,2)"); break; } case 6:{ puts("POUR(2,1)"); break; } } } } else puts("impossible"); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator