package test;

//对于水壶问题的定义的几个操作：
//0. 　空操作
//1.　4加仑壶不满时将其加满
//2.　3加仑壶不满时将其加满
//3.　把4加仑水壶中的水全部倒出
//4.　把3加仑水壶中的水全部倒出
//5. 把3加仑水壶中的水往4加仑水壶中倒，直到4加仑水壶满
//6. 把4加仑水壶中的水往3加仑水壶中倒，直到3加仑水壶满
//7. 把3加仑水壶中的水全部倒往4加仑水壶中
//8. 　 把4加仑水壶中的水全部倒往3加仑水壶中

//解决的基本思路是利用有限状态机M，设X为4加仑水壶的水量，Y是3加仑水壶的水量
//则所有可能的(X，Y)序对作为M的状态集，操作{1,2，3,4，5,6，7,8}是输入字符集
//,开始状态是(0,0)，终止状态是{(2，Y)}，Y可能是0,1，2,3。
//当一个输入串是M的语言时，这个串就是水壶问题的一个可能方案。

//编程的考虑是：Water[5][4]标识数组，为1时，表示这个状态已经到达，为0时表示这个状态
//没有到达。
//

////////////////源代码，在JAVA SE v1.4.2_01下调试通过///////////////
//package pot;

import java.io.*;
import java.lang.*;

public class Pot
{
private int X; //4加仑水壶的水量
private int Y; //3加仑水壶的水量

int x1,y1; //保存上一次的状态

final int MAX_STACKA=3000;

private int[] Stack=new int[MAX_STACKA];//存放状态和操作的堆栈
private int SPo=0; //堆栈指针

private int[][] Water=new int[5][4];//描述状态是否已经访问的数组

static int count_finish=0; //记下第几个解决方案

public Pot()
{
X=0;
Y=0;
solve();
}

public void solve()
{System.out.println("正在计算水壶问题.......");


for(int i=1;i<=8;i++) {
              System.out.println("....."+i+".....");
              for(int k=0;k<=4;k++)        //状态清零
                     for(int j=0;j<=3;j++) Water[k][j]=0;
            
              X=0;
              Y=0;
              Water[X][Y]=1;     
              SPo=0;
              push(X,Y,0);
              sheni(i);
              }
}

private void sheni(int op)
{
    x1=X;         //保存上一个状态对
    y1=Y;
    operate(op); //进行操作

            if(X==2) {                //到达目标状态
                    push(X,Y,op);
                     finish();
                      pop();
                     X=x1;
                                            Y=y1;  
                      return;
                    }
         else if(Water[X][Y]==1) { //已经访问这个状态，返回
               X=x1;Y=y1;
               if(op==8) pop();     //这层的8个操作都进行了一遍，返回上一层
               return;
              }
        else {
             Water[X][Y]=1;
             push(X,Y,op);
             try{
             for(int j=1;j<=8;j++) sheni(j); //在这一层展开，试探8个操作是否有某一个成功
             }
             catch(ArrayIndexOutOfBoundsException e){}
             return;
            }
}

private void finish()   //成功找到一个解决方案，打印出来
{
count_finish++;
System.out.println("第"+count_finish+"种解决方案：");
System.out.println("4加仑水壶"+"\t3加仑水壶"+"\t所使用的操作");
int i;
for(i=0;i<=SPo-3;i=i+3) System.out.println(Stack[i]+"\t\t"+Stack[i+1]+"\t\t"+Stack[i+2]);
}                

private void push(int x,int y,int op) //入栈
{
   Stack[SPo]=x;
   SPo++;
   Stack[SPo]=y;
   SPo++;
   Stack[SPo]=op;
   SPo++;
}

private void pop()    //出栈
{
   SPo--;
   SPo--;
   Y=Stack[SPo];
   SPo--;
   X=Stack[SPo];
}

//定义操作
private void operate(int op)
{
switch(op) {
case 1:X=4;
      break;
case 2:Y=3;
      break;
case 3:X=0;
      break;
case 4:Y=0;
      break;
case 5:int i;
        if(X+Y>=4) {
          i=4-X;
          X=4;
          Y=Y-i;
          }
        else {
          X=X+Y;
          Y=0;
        }
       break;
case 6:int j;
        if(X+Y>=3) {
          j=3-Y;
          Y=3;
          X=X-j;
          }
        else {
          Y=X+Y;
          X=0;
        }
       break;
   case 7:
       X=X+Y;
       Y=0;
       break;
   case 8:Y=Y+X;
       X=0;
       break;
   default:
}
}
        

public static void main(String[] args)
{
Pot ont=new Pot();
}
}