倒水问题-白红宇

倒水问题

阅读量：5936 次

发布时间：2019-06-19

本文共 1876 字，大约阅读时间需要 6 分钟。

设大，中，小3个杯子的容量分别为a，b，c。最初只有大杯子装满水，其他两个为空。最少要多少步让某一个杯子中有x升。0<c<b<a<1000

输入:

6 3 1

10 7 3

输出:

6 0 0

3 3 0

3 2 1

4 2 0

minimum steps:3

10 0 0

3 7 0

3 4 3

6 4 0

6 1 3

9 1 0

9 0 1

2 7 1

2 5 3

minimum steps:8

1 #include
     
       2 #include
      
        3 #include
       
         4 #define mem(a) memset(a,0,sizeof(a)) 5 using namespace std; 6 const int MAXN=1000+10; 7 int q[MAXN*MAXN],fa[MAXN][MAXN],vis[MAXN][MAXN],step[MAXN][MAXN]; 8 int a,b,c,m; 9 void print(int state)//打印步骤10 {11     int x=state/1000,y=state%1000,z;12     z=a-x-y;13     if(state==q[0]){14         cout<
        
         <
         
          <<" "<
          
           <
           
            <<" "<
            
             <
             
              <
              
               =b-y)v=(x-(b-y))*1000+b;else v=x+y;//把a的倒进b42 if(!vis[v/1000][v%1000])//如果没有搜索到过43 {44 vis[v/1000][v%1000]=1;//标记已走过45 q[rear++]=v;//放入队列尾部46 fa[v/1000][v%1000]=u;//记录父节点47 step[v/1000][v%1000]=step[x][y]+1;//步数加一48 }49 if(x>=c-z)v=(x-(c-z))*1000+y;else v=y;//把a的倒进c50 if(!vis[v/1000][v%1000]){vis[v/1000][v%1000]=1;q[rear++]=v;fa[v/1000][v%1000]=u;step[v/1000][v%1000]=step[x][y]+1;}51 }52 if(y)//b不为空53 { 54 v=(x+y)*1000;//b倒进a55 if(!vis[v/1000][v%1000]){vis[v/1000][v%1000]=1;q[rear++]=v;fa[v/1000][v%1000]=u;step[v/1000][v%1000]=step[x][y]+1;}56 if(y>=c-(z))v=x*1000+(y-(c-(z)));else v=x*1000;//b倒进c57 if(!vis[v/1000][v%1000]){vis[v/1000][v%1000]=1;q[rear++]=v;fa[v/1000][v%1000]=u;step[v/1000][v%1000]=step[x][y]+1;}58 }59 if(z)//c不为空60 {61 v=(x+z)*1000+y;//c倒进a62 if(!vis[v/1000][v%1000]){vis[v/1000][v%1000]=1;q[rear++]=v;fa[v/1000][v%1000]=u;step[v/1000][v%1000]=step[x][y]+1;}63 if(z>=b-y)v=x*1000+b;else v=x*1000+a-x;//c倒进b64 if(!vis[v/1000][v%1000]){vis[v/1000][v%1000]=1;q[rear++]=v;fa[v/1000][v%1000]=u;step[v/1000][v%1000]=step[x][y]+1;}65 }66 }67 }68 int main()69 {70 while(cin>>a>>b>>c>>m)71 {72 bfs();73 cout<