poj3414——Pots

44424742

绝对的BFS好题！在实验室师兄的启发下，1A！
代码有点长...
#include<stdio.h>#include<string.h>struct node{int u1,u2,step;}tt[10000];bool vis[105][105];int a,b,c,front=0,rear=0;int pre[10000];void pri(int front){int i,top=1,s,x,y;struct node kk[1000];kk[top]=tt[front];s=pre[front];while(s!=-1){kk[++top]=tt[s];s=pre[s];}printf("%d\n",top-1);for(i=top-1;i>0;i--){int k=kk[i].step ;switch(k){case 1:printf("FILL(1)\n");break;case 2:printf("DROP(1)\n");break;case 3:printf("POUR(1,2)\n");break;case 4:printf("FILL(2)\n");break;case 5:printf("DROP(2)\n");break;default :printf("POUR(2,1)\n");break;}}}void solve(){int i,tempx,tempy,x,y;bool flag=true;memset(pre,-1,sizeof(pre));scanf("%d%d%d",&a,&b,&c);rear++;tt[rear].u1=0;tt[rear].u2=0;tt[rear].step =-1;memset(vis,true,sizeof(vis));vis[0][0]=false;while(rear!=front){front++;x=tt[front].u1;y=tt[front].u2;if(x+y==c||x==c||y==c){pri(front);flag=false;break;}for(i=1;i<=6;i++){switch(i){case 1:if(x<a){tempx=a;tempy=y;if(vis[tempx][tempy]){vis[tempx][tempy]=false;tt[++rear].u1=tempx;tt[rear].u2=tempy;tt[rear].step =i;pre[rear]=front;}}break;case 2:if(x>0){tempx=0;tempy=y;if(vis[tempx][tempy]){vis[tempx][tempy]=false;tt[++rear].u1=tempx;tt[rear].u2=tempy;tt[rear].step =i;pre[rear]=front;}}break;case 3:if(x>0&&y<b){if(b-y>=x){tempx=0;tempy=y+x;if(vis[tempx][tempy]){vis[tempx][tempy]=false;tt[++rear].u1=tempx;tt[rear].u2=tempy;tt[rear].step =i;pre[rear]=front;}}else {tempx=x-(b-y);tempy=b;if(vis[tempx][tempy]){vis[tempx][tempy]=false;tt[++rear].u1=tempx;tt[rear].u2=tempy;tt[rear].step =i;pre[rear]=front;}}}break;case 4:if(y<b){tempx=x;tempy=b;if(vis[tempx][tempy]){vis[tempx][tempy]=false;tt[++rear].u1=tempx;tt[rear].u2=tempy;tt[rear].step =i;pre[rear]=front;}}break;case 5:if(y>0){tempx=x;tempy=0;if(vis[tempx][tempy]){vis[tempx][tempy]=false;tt[++rear].u1=tempx;tt[rear].u2=tempy;tt[rear].step =i;pre[rear]=front;}}break;default :if(y>0&&x<a){if(a-x>=y){tempx=x+y;tempy=0;if(vis[tempx][tempy]){vis[tempx][tempy]=false;tt[++rear].u1=tempx;tt[rear].u2=tempy;tt[rear].step =6;pre[rear]=front;}}else {tempx=a;tempy=y-(a-x);if(vis[tempx][tempy]){vis[tempx][tempy]=false;tt[++rear].u1=tempx;tt[rear].u2=tempy;tt[rear].step =6;pre[rear]=front;}}}break;}}}if(flag)printf("impossible\n");}int main(){solve();return 0;}