题解：总共是有6种可能，所以直接列出来bfs就可以，注意数据大小都在100一下。注意队列的大小
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> /* 题解，总共有六种情况，bfs FILL(i) FILL(j) DROP(i) DROP(j) POUR(i,j) POUR(j,i) */ using namespace std; struct node { int a; //代表a的水 int b; //代表b的水 int x;//从1到6代表六种种操作 int per; //前驱 }; int main() { int n,m,k; int i,j; int head,tail; int ans=-1; int vis[110][110]; int f[1110]; while(scanf("%d%d%d",&n,&m,&k)!=EOF) { memset(vis,0,sizeof(vis)); memset(f,0,sizeof(f)); struct node que[40000]; head=0; tail=1; ans=-1; que[0].a=0; que[0].b=0; vis[0][0]=1; while(head<4000&&tail<399950) { int k1=que[head].a,k2=que[head].b; //1 if(vis[n][k2]==0) { que[tail].a=n; que[tail].b=k2; que[tail].per=head; que[tail].x=1; if(que[tail].a==k||que[tail].b==k) { ans=tail; break; } tail++; vis[n][k2]=1; } //2 if(vis[k1][m]==0) { que[tail].a=k1; que[tail].b=m; que[tail].x=2; que[tail].per=head; if(que[tail].a==k||que[tail].b==k) { ans=tail; break; } tail++; vis[k1][m]=1; } //3 if(vis[0][k2]==0) { que[tail].a=0; que[tail].b=k2; que[tail].x=3; que[tail].per=head; if(que[tail].a==k||que[tail].b==k) { ans=tail; break; } tail++; vis[0][k2]=1; } //4 if(vis[k1][0]==0) { que[tail].a=k1; que[tail].b=0; que[tail].x=4; que[tail].per=head; if(que[tail].a==k||que[tail].b==k) { ans=tail; break; } tail++; vis[k1][0]=1; } //5POUR(a,b)从a倒入b int temp=k1+k2; int newa,newb; if(temp>m) { newa=temp-m; newb=m; } else { newa=0; newb=temp; } if(vis[newa][newb]==0) { que[tail].a=newa; que[tail].b=newb; que[tail].x=5; que[tail].per=head; if(que[tail].a==k||que[tail].b==k) { ans=tail; break; } tail++; vis[newa][newb]=1; } //6POUR(b,a)从b倒入a if(temp>n) { newa=n; newb=temp-n; } else { newa=temp; newb=0; } if(vis[newa][newb]==0) { que[tail].a=newa; que[tail].b=newb; que[tail].x=6; que[tail].per=head; if(que[tail].a==k||que[tail].b==k) { ans=tail; break; } tail++; vis[newa][newb]=1; } head++; } if(ans!=-1) { int sum=0,root=ans; while(root!=0) { f[sum]=que[root].x; sum++; root=que[root].per; } printf("%d\n",sum); for(i=sum-1; i>=0; i--) { if(f[i]==1) { printf("FILL(1)\n"); } if(f[i]==2) { printf("FILL(2)\n"); } if(f[i]==3) { printf("DROP(1)\n"); } if(f[i]==4) { printf("DROP(2)\n"); } if(f[i]==5) { printf("POUR(1,2)\n"); } if(f[i]==6) { printf("POUR(2,1)\n"); } } } else { printf("impossible\n"); } } }
