以前小时候的智力题。。。。
题目大意：
这个就是以前的接水问题嘛，给你两个锅，装满分别为a，b升水(c<=max(a,b)<=100)，问你怎么装出c升水。问你最少的操作步数，并按顺序输出这些操作。
广搜呗，然后在找到终点之后，要输出路径。这里我是用的两个数组并且给所有入过队的状态编号：
id为i的状态执行的操作为f[i] id为i的状态的上一个状态的id为last[i]
#include<iostream> #include<math.h> #include<string.h> #include<queue> #define N 110 using namespace std; int a,b,e; struct time//此时刻，两个锅分别装水ab，已经进行了step步操作 { int a; int b; int id; }; queue<time>q; int f[N*N]={0};//id为i的状态执行的操作为f[i] int last[N*N]={0};//id为i的状态的上一个状态为last[i] bool vis[N][N]={0}; int dis[N][N]={0}; time move(int i,time t) { time x=t; if(i==0) { x.a=a; } if(i==1) { x.b=b; } if(i==2)//把b倒进a { if(x.a+x.b>a) { int t=x.a; x.a=a; x.b=t+x.b-a; } else { x.a=x.a+x.b; x.b=0; } } if(i==3)//把a倒进b { if(x.a+x.b>b) { int t=x.b; x.b=b; x.a=x.a+t-b; } else { x.b=x.a+x.b; x.a=0; } } if(i==4) { x.a=0; } if(i==5) { x.b=0; } return x; } void output(int n,int step) { int out[N*N]={0}; for(int i=step;i>0;i--) { out[i]=f[n]; n=last[n]; } for(int i=1;i<=step;i++) { if(out[i]==0) { cout<<"FILL(1)"<<endl; } if(out[i]==1) { cout<<"FILL(2)"<<endl; } if(out[i]==2) { cout<<"POUR(2,1)"<<endl; } if(out[i]==3) { cout<<"POUR(1,2)"<<endl; } if(out[i]==4) { cout<<"DROP(1)"<<endl; } if(out[i]==5) { cout<<"DROP(2)"<<endl; } } } bool find(time x) { if(x.a==e||x.b==e)return 1; return 0; } int main() { while(cin>>a>>b>>e) { int step; bool flag=0; int n=2; time l; l.a=0; l.b=0; l.id=1; f[1]=1; dis[0][0]=1; vis[0][0]=1; q.push(l); while(!q.empty()) { if(flag==1)break; for(int i=0;i<6;i++)//4中操作 { time t; t=move(i,q.front()); //cout<<t.a<<" "<<t.b<<endl; t.id=n; if(vis[t.a][t.b]==1)continue; if(find(t)) { flag=1; step=dis[q.front().a][q.front().b]; } q.push(t); dis[t.a][t.b]=dis[q.front().a][q.front().b]+1; vis[t.a][t.b]=1; f[n]=i; last[n]=q.front().id; n++; //cout<<n; if(flag==1)break; } q.pop(); } if(flag==1) { cout<<step<<endl; output(n-1,step); } else { cout<<"impossible"<<endl; } memset(vis,0,sizeof(vis)); memset(dis,0,sizeof(dis)); memset(f,0,sizeof(f)); memset(last,0,sizeof(last)); while(!q.empty()) { q.pop(); } } }
注意：ab不可交换，ab不可交换，ab不可交换！
