本来挺简单的一道题,但是马虎wa了一次!
根据题意采取广搜的方法,代码有点长,但自我感觉思路挺清晰的!
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; typedef struct fun { int pre; int a,b; int sign; }rr; fun s[10005]; void print(int j) { if(s[j].pre!=-1) { print(s[j].pre); switch(s[j].sign) { case 1:printf("fill A\n");break; case 2:printf("fill B\n");break; case 3:printf("empty A\n");break; case 4:printf("empty B\n");break; case 5:printf("pour A B\n");break; case 6:printf("pour B A\n");break; } } } void dfs(int ca,int cb,int n) { int i,j,l; i=0; s[i].a=0; s[i].b=0; s[i].pre=-1; s[i].sign=0; j=1; int sign; for(i=0; i<j; i++) { if(s[i].a!=ca)//填满a { sign=0; for(l=0; l<j; l++) { if(s[l].a==ca && s[l].b==s[i].b)//以前已经存在了 { sign=1;break; } } if(sign==0) { s[j].a=ca;s[j].b=s[i].b;s[j].pre=i;s[j].sign=1; if(s[j].a==n || s[j].b==n)//跳出来就不用管j了 break; j++; } } if(s[i].b!=cb)//填满b { sign=0; for(l=0; l<j; l++) { if(s[l].a==s[i].a && s[l].b==cb) { sign=1;break; } } if(sign==0) { s[j].a=s[i].a;s[j].b=cb;s[j].pre=i;s[j].sign=2; if(s[j].a==n || s[j].b==n)//跳出来就不用管j了 break; j++; } } if(s[i].a!=0)//腾空a { sign=0; for(l=0; l<j; l++) { if(s[l].a==0 && s[l].b==s[i].b) { sign=1;break; } } if(sign==0) { s[j].a=0;s[j].b=s[i].b;s[j].pre=i;s[j].sign=3; if(s[j].a==n || s[j].b==n)//跳出来就不用管j了 break; j++; } } if(s[i].b!=0) { sign=0; for(l=0; l<j; l++) { if(s[l].a==s[i].a && s[l].b==0) { sign=1;break; } } if(sign==0) { s[j].a=s[i].a;s[j].b=0;s[j].pre=i;s[j].sign=4; if(s[j].a==n || s[j].b==n)//跳出来就不用管j了 break; j++; } } int x,y; if(s[i].a!=0 && s[i].b!=cb) { sign=0; y=s[i].b+s[i].a>cb?cb:s[i].b+s[i].a; x=s[i].b+s[i].a-cb>0?s[i].b+s[i].a-cb:0; for(l=0; l<j; l++) { if(s[l].a==x && s[l].b==y) { sign=1;break; } } if(sign==0) { s[j].a=x;s[j].b=y;s[j].pre=i;s[j].sign=5; if(s[j].a==n || s[j].b==n)//跳出来就不用管j了 break; j++; } } if(s[i].a!=ca && s[i].b!=0) { sign=0; x=s[i].b+s[i].a>ca?ca:s[i].b+s[i].a; y=s[i].b+s[i].a-ca>0?s[i].b+s[i].a-ca:0; for(l=0; l<j; l++) { if(s[l].a==x && s[l].b==y) { sign=1;break; } } if(sign==0) { s[j].a=x;s[j].b=y;s[j].pre=i;s[j].sign=6; if(s[j].a==n || s[j].b==n)//跳出来就不用管j了 break; j++; } } } print(j); if(s[j].a==n && s[j].b!=n) { if(s[j].b!=0) printf("empty B\n"); printf("pour A B\n"); } printf("success\n"); return; } int main() { int ca,cb,n; while(scanf("%d%d%d",&ca,&cb,&n)!=EOF) { if(cb==n) printf("fill B\nsuccess\n"); else dfs(ca,cb,n); } return 0; }