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