高分：分油问题，c++怎么编程？

Question

有三个大小不等的，没有刻度的瓶子，分别能装x，y，z升水。开始时，x装满水，y和z两个为空。要求找出一种步骤最少的分水方法，在某个桶上分出t升水。（为方便，假设x、y、z、t都为整数）
要求

① 输入为三个瓶子的装水量（例如分别是10、7、2L）和需要分出的水量t 升（如4 L）。
② 若能够分得t升水，输出分水的详细过程，要求分水步骤数最少。
③ 若不能分得t升水，输出“不可能”。
用C++编程，要求完整能直接运行

Answer 1

#include <stdio.h>
#include <string.h>
int vol1,vol2,vol3,cur1,cur2,cur3,flag=0,goal,curb1,curb2,curb3;
int map[100][100][100];
int x[10000]; //记录每一步的倒油操作,1到2表示为1，1到3表示为2,2到1表示为3,2到3表示为4,3到1表示为5,3到2表示为6 
void push(int *t1, int *t2,int v2) //把 *t1和*t2为当前油量,v2为*t2所在容器的容量。 
{if(  v2>*t1+*t2){*t2=*t2+*t1;*t1=0;}
 else {  *t2=*t2+*t1;*t1=*t2-v2;*t2=v2;}
}
void print(int step)
{printf("%d %d %d\n",curb1,curb2,curb3);
  for(int i=1;  i<step;i++)
  switch(x[i])
   { case 1: 
              push(&curb1,&curb2,vol2);
            printf("%d %d %d\n",curb1,curb2,curb3);
            break;
     case 2: 
            push(&curb1,&curb3,vol3);
            printf("%d %d %d\n",curb1,curb2,curb3);
            break;
     case 3: 
            push(&curb2,&curb1,vol1);
            printf("%d %d %d\n",curb1,curb2,curb3);
            break;
     case 4: 
            push(&curb2,&curb3,vol3);
            printf("%d %d %d\n",curb1,curb2,curb3);
            break;
     case 5: 
            push(&curb3,&curb1,vol1);
            printf("%d %d %d\n",curb1,curb2,curb3);
            break;
     case 6: 
            push(&curb3,&curb2,vol2);
            printf("%d %d %d\n",curb1,curb2,curb3);
            break;
     
   }
     
}
void backtrack(int step)
{ int t1=cur1,t2=cur2,t3=cur3;  
   if(flag) return;
   if(  t1==goal||t2==goal||t3==goal)
    { print(step);flag=1;return; }
  //开始尝试1倒到2 
    push(&cur1,&cur2,vol2);
    if(!map[cur1][cur2][cur3])
    {x[step]=1;map[cur1][cur2][cur3]=1;
     backtrack(step+1); 
    }
    cur1=t1;cur2=t2;cur3=t3;
   //结束1倒到2，恢复各容器的原来油量 
  //开始尝试1倒到3 
      push(&cur1,&cur3,vol3);
    if(!map[cur1][cur2][cur3])
    {  x[step]=2;map[cur1][cur2][cur3]=1;
         backtrack(step+1); 
    }
    cur1=t1;cur2=t2;cur3=t3;
  //结束1倒到3，恢复各容器的原来油量 
  //开始尝试2倒到1 
    push(&cur2,&cur1,vol1);
    if(!map[cur1][cur2][cur3])
    {x[step]=3;map[cur1][cur2][cur3]=1;
     backtrack(step+1); 
    }
    cur1=t1;cur2=t2;cur3=t3;
  //结束2倒到1，恢复各容器的原来油量
  //开始尝试2倒到3
    push(&cur2,&cur3,vol3);
    if(!map[cur1][cur2][cur3])
    {x[step]=4;map[cur1][cur2][cur3]=1;
     backtrack(step+1); 
    }
    cur1=t1;cur2=t2;cur3=t3;
  //结束2倒到3，恢复各容器的原来油量
  //开始尝试3倒到1 
    push(&cur3,&cur1,vol1);
    if(!map[cur1][cur2][cur3])
    {x[step]=5;map[cur1][cur2][cur3]=1;
     backtrack(step+1); 
    }
    cur1=t1;cur2=t2;cur3=t3;
  //结束3倒到1，恢复各容器的原来油量
  //开始尝试3倒到2 
    push(&cur3,&cur2,vol2);
    if(!map[cur1][cur2][cur3])
    {x[step]=6;map[cur1][cur2][cur3]=1;
     backtrack(step+1); 
    }
    cur1=t1;cur2=t2;cur3=t3;
  //结束3倒到2，恢复各容器的原来油量
}
  
int main()
{scanf("%d%d%d%d%d%d%d",&vol1,&vol2,&vol3,&cur1,&cur2,&cur3,&goal);
 memset(map,0,sizeof(map));
 map[cur1][cur2][cur3]=1;
   curb1=cur1;curb2=cur2;curb3=cur3;
 backtrack(1);
 if(  !flag)
 printf("impossible");
}

输入：

3行
第1行是3个整数，由大到小，表示3个容器的容量
第1行是3个整数，表示3个容器的原有油量
第3行是1个整数，表示要求得到的油量（放在哪个容器里得到都可以）

输出：

实现过程中的各个状态(即各个容器的油量)。答案不唯一。
如果没有可能实现，则输出：“impossible”。

Answer 2

今天实验了一下，写出了一半吧。就是这个求最优解就太困难了，而且记录求解路径很困难。这种题遇到不是一次两次了，有喜欢的大家一起交流交流经验。

Answer 3

能强行写出，不过程序优化就等等吧