今天在网上浏览，发现一个很好玩的问题，水杯倒水问题：

有3个容器，各是20升，13升，7升， 形状不同也不透明。一开始20升的容器里面装了20升水，反正倒来倒去最后要让20升和13升容器各装了10升水

想了好长时间，终于写出了步骤:

 20      0       0
 7       13      0
 7       6       7
 14      6       0
 14      0       6
 1       13      6
 1       12      7
 8       12      0
 8       5       7
 15      5       0
 15      0       5
 2       13      5
 2       11      7
 9       11      0
 9       4       7
 16      4       0
 16      0       4
 3       13      4
 3       10      7
 10      10      0

网上找到的算法实现如下：用宽度优先搜索 BFS的思想

#include "stdafx.h"

#include   <iostream> 
#include   <cstring> //   for   memset   and   memcmp

//from http://blog.csdn.net/bat603

#define   MIN(a,b)   (((a)   <   (b))   ?   (a)   :   (b)) 
#define   HASH(s)   hash[s.vol[0]][s.vol[1]][s.vol[2]] 

struct   state 
{ 
    int   vol[3]; 
    int   depth; 
    int   parent; 
}; 

//瓶子的容量
const   int   capacity[3]   =   {20,   17,   3}; 
const   int   QUEUE_SIZE   =   100000; 

state   queue[QUEUE_SIZE]; //   for   bfs 

void   print_answer(int   k) 
{ 
    int   stack[100]; 
    int   p   =   0; 
    int   j; 
   
    while   (k   !=   -1) 
    { 
        stack[p++]   =   k; 
        k   =   queue[k].parent; 
    } 
   
    while   (p--) 
    { 
        std::cout   <<   "Step   "   <<   queue[stack[p]].depth   <<   ":/t"; 
       
        for   (j=0;   j<3;   j++) 
        { 
            std::cout   <<   queue[stack[p]].vol[j]   <<   '/t'; 
        } 
       
        std::cout   <<   std::endl; 
    } 
} 

int   main(void) 
{ 
    static   short   int   hash[100][100][100]; //   for   quick   check 
    state   start,   target,   current; 
   
    int   open,   tail; 
    int   i,   j; 
    int   delta; 
   
    //   data   set 
    start.vol[0]   =   20;  //开始时水的体积
    start.vol[1]   =   0; 
    start.vol[2]   =   0; 
    start.depth   =   0; 
    start.parent   =   -1; 
   
    target.vol[0]   =   10;  //结果的存放，目前是第一个瓶和第二瓶存放
    target.vol[1]   =   10; 
    target.vol[2]   =   0; 
   
    //   initialization 
    memset(hash,   0,   sizeof(hash)); 
    queue[0]   =   start; 
    open   =   0,   tail   =   1; 
    HASH(start)   =   1; 
   
    //   bfs   search! 
    while   (open   <   tail) 
    { 
        for   (i=0;   i<3;   i++) 
        { 
            for   (j=0;   j<3;   j++) 
            { 
                if   (i   !=   j) 
                { 
                    current   =   queue[open]; 
                   
                    //   from   i   to   j 
                    delta   =   MIN(current.vol[i],   capacity[j]   -   current.vol[j]); 
                    current.vol[i]   -=   delta; 
                    current.vol[j]   +=   delta; 
                   
                    if   (!HASH(current))   //   not   duplicated 
                    { 
                        current.depth++; 
                        current.parent   =   open; 
                        queue[tail++]   =   current; //   enqueue 
                        HASH(current)   =   1; 
                       
                        if   (memcmp(&current.vol,   &target.vol,   sizeof(current.vol))   ==   0) //   got   it 
                        { 
                            print_answer(tail   -   1); 
                            return   0; 
                        } 
                       
                    } 
                } 
            } 
        } 
       
        open++; 
    } 
   
    std::cout   <<   "no   solution   found"   <<   std::endl; 
    return   1; 
}