import java.io.*;
import java.util.*;

/*建立數(shù)據(jù)結(jié)構(gòu):RiverSide*/

class RiverSide {

    int Cannibal;
    int Missionary;

       public RiverSide() { 

       }

       public String toString() {  //不會輸出散列碼
           return " Cannibal " + Cannibal + " Missionary " + Missionary;

       }

}

/*建立數(shù)據(jù)結(jié)構(gòu):Boat*/

class Boat {

    int Cannibal;
    int Missionary;

        public Boat() {

        }

        public Boat( int Cannibal , int Missionary ) {
            this.Cannibal = Cannibal;
            this.Missionary = Missionary;
        }

}

/*建立數(shù)據(jù)結(jié)構(gòu):Node*/

class Node {

  int f , h , steps , id , parentid;
  Boat boat;
  RiverSide riverside1;
  RiverSide riverside2;
  int side;

      public Node() {
      
      }
      
      public Node( int f , int h , int steps , Boat boat , RiverSide riverside1 , RiverSide riverside2 , int side , int id , int parentid ) {
          this.f = f;
          this.h = h;
          this.steps = steps;
          this.boat = boat;
          this.riverside1 = riverside1;
          this.riverside2 = riverside2;
          this.side = side;
          this.id = id;
          this.parentid = parentid;

      }
      
}

/*主類Missionary And Cannibal Pass Solution*/

class MACPS {

    public Vector Open=new Vector();
    public Vector Close=new Vector();
    int id = 0;

        public void getSolutionStep() {

            Boat boat1 = new Boat();
            Boat boat2 = new Boat();
            RiverSide riverside1 = new RiverSide();
            RiverSide riverside2 = new RiverSide();
            RiverSide riverside3 = new RiverSide();
            RiverSide riverside4 = new RiverSide();
            boolean flag =true;

                Node Source = new Node( 0 , 0 , 0 , boat1 , riverside1 , riverside2 , 0 , 0 , 0 );  	//初始化起始節(jié)點

                    Source.riverside1.Cannibal = 3;
                    Source.riverside1.Missionary = 3;
                    Source.riverside2.Cannibal = 0;
                    Source.riverside2.Missionary = 0;
                    Source.boat.Cannibal = 0;
                    Source.boat.Missionary = 0;
                    Source.side = 1;
                    Source.id = 0;
                    Source.parentid = 0;
                    Source.h = 4;
                    Source.f = 4;
                    Source.steps = 0;

                Node Target = new Node( 0 , 0 , 0 , boat2 , riverside3 , riverside4 , 0 , 0 , 0 );   	//初始化目標(biāo)節(jié)點
                    Target.riverside1.Cannibal=0;
                    Target.riverside1.Missionary=0;
                    Target.riverside2.Cannibal=3;
                    Target.riverside2.Missionary=3;
                    Target.boat.Cannibal=0;
                    Target.boat.Missionary=0;

                push( Source , Open );
                Node Current = Source;
                while( flag == true ) {                       
                    if( Open.isEmpty() ) {	//表頭為空結(jié)束循環(huán)
                        flag = false;
                        break;
                        
                    }
                    
                    Current = pop( Open );
                    push( Current , Close );
                    if( isTarget( Current , Target ) )    //比較是否是目標(biāo)節(jié)點    
                        break;
                    extend( Current , Target , Open );    //擴展OPEN中的節(jié)點       
                    atFirstOpen();                        //將OPEN排序        
                
                }

                Node Father;               //從目標(biāo)節(jié)點通過Father節(jié)點找出合法算符,繼續(xù)擴展Father
                Vector Result = new Vector();
                if( flag == true ) {
                    Result.add( Current );
                    int m = Current.parentid;
                    int k = 0;
                    
                        while( m > 0 ) {
                            Father = found( m , Close , Target );
                            Result.add( Father );
                            m = Father.parentid;
                            k++;
                            
                        }
                    
                }
                
                else {
                   System.out.print("solution isn't found");
                   
                                  }
                
              Result.add(Source);
              Stack aaa = new Stack();
              Stack bbb = new Stack();
              Stack ccc = new Stack();
                  for( int i = 0; i < Result.size(); i++ ) {
                      /*System.out.println( ( (Node)Result.get(i) ).riverside1 + " " + " withboat: " + ( (Node)Result.get(i) ).side 
 + "--------" + ( (Node)Result.get(i) ).riverside2 );      */               
                      aaa.push( ( (Node)Result.get(i) ).riverside1 );
                      bbb.push( ( (Node)Result.get(i) ).side );
                      ccc.push( ( (Node)Result.get(i) ).riverside2 );
                      
                  }

                  for( int i = 0; i < Result.size(); i++ ) {
                      System.out.println("Left Side: " + aaa.pop() + " withboat: " + bbb.pop() + "\n" );
                      System.out.println("Right Side: " + ccc.pop() + "\n\n");

                  }

               
        }
        
        public void push( Node sour , Vector open ) {
            open.add( sour );
             
        }

        public Node pop( Vector open ) {             Node firstnode = (Node)open.get(0);
            open.removeElementAt(0);
                return firstnode;
        }

        public boolean isTarget( Node cur,Node tar ) {
            if( cur.riverside1.Cannibal == tar.riverside1.Cannibal && cur.riverside1.Missionary == tar.riverside1.Missionary && cur.side == tar.side )
                return true;
            else 
                return false;
        }

        public void extend( Node current , Node tar , Vector open ) {    //找出下一步合法操作，并擴展節(jié)點

            int nCannibal1 = 0;
            int  nMissionary1 = 0;
            int nCannibal2 = 0;
            int  nMissionary2 = 0;
            int i;

            Boat boatState[] = new Boat [5];
            for( i = 0; i < 5;i++ )
                boatState[i] = new Boat();

            if(current.side==1) {	//盡量多的去到目標(biāo)河岸，運2個的操作符優(yōu)先，野人優(yōu)先                                     
                boatState[0].Cannibal = 2;
                boatState[0].Missionary = 0;
                boatState[1].Cannibal = 1;
                boatState[1].Missionary = 1;
                boatState[2].Cannibal = 0;
                boatState[2].Missionary = 2;
                boatState[3].Cannibal = 1;
                boatState[3].Missionary = 0;
                boatState[4].Cannibal = 0;
                boatState[4].Missionary = 1;

            }

            else {	//盡量少的回來，運1個的操作符優(yōu)先
                boatState[0].Cannibal = 0;
                boatState[0].Missionary = 1;
                boatState[1].Cannibal = 1;
                boatState[1].Missionary = 0;
                boatState[2].Cannibal = 0;
                boatState[2].Missionary = 2;
                boatState[3].Cannibal = 1;
                boatState[3].Missionary = 1;
                boatState[4].Cannibal = 2;
                boatState[4].Missionary = 0;
          }

        boolean  flag = true;
        int j;
            for( j = 0; j < 5; j++ ) {
                if(current.side==1) { //船在岸就運人過去，就做“-”運算
                    nCannibal1 = current.riverside1.Cannibal - boatState[j].Cannibal;
                    nMissionary1 = current.riverside1.Missionary - boatState[j].Missionary;
                    
                }
                 
                else {	//船不在岸運人過來，做“+”運算
                    nCannibal1 = current.riverside1.Cannibal + boatState[j].Cannibal;
                    nMissionary1 = current.riverside1.Missionary + boatState[j].Missionary;
                }
                //對岸的人數(shù)
                nCannibal2 = 3 - nCannibal1;
                nMissionary2 = 3 - nMissionary1;

                if( ( nCannibal1 <= nMissionary1 || nMissionary1 == 0 ) && ( nCannibal2 <= nMissionary2 || nMissionary2 == 0 ) && nCannibal1 >= 0 && nMissionary1 >= 0 && nCannibal2 >= 0 && nMissionary2 >= 0 ) { 	//判斷擴展的節(jié)點是否合法。即野人少于傳教士
                    if(j<5) {
                        current.boat.Cannibal = boatState[j].Cannibal;
                        current.boat.Missionary = boatState[j].Missionary;
                        Boat boat = new Boat();
                        RiverSide riverside1 = new RiverSide();
                        RiverSide riverside2 = new RiverSide();

                        Node next = new Node( 0 , 0 , 0 , boat , riverside1 , riverside2 , 0 , 0 , 0 );

                            next.riverside1.Cannibal = nCannibal1;
                            next.riverside1.Missionary = nMissionary1;
                            next.riverside2.Cannibal = nCannibal2;
                            next.riverside2.Missionary = nMissionary2;
                            next.boat.Cannibal = 0;
                            next.boat.Missionary = 0;
                            next.id = ++id;
                            next.parentid = current.id;
                            next.steps = current.steps+1;
                            if( next.steps%2 == 0 )
                                next.side = 1;
                            else
                                next.side = 0;
                            next.h = next.riverside1.Cannibal+next.riverside1.Missionary - 2*next.side;
                            next.f = next.h + next.steps;
                            if( next.id != 0 ) { 	//判斷擴展節(jié)點是否在Close中                                     
                                int k = 0;
                               
                                    while( ( k<Close.size() ) ) {
                                        if( ( next.riverside1.Cannibal != ( (Node)( Close.get(k) ) ).riverside1.Cannibal) || 
( next.riverside1.Missionary != ( (Node)( Close.get(k) ) ).riverside1.Missionary ) || ( next.side != ( (Node)(Close.get(k) ) ).side ) )
                                            flag = false;
                                        else
                                            flag = true;
                                        if( flag == true )
                                            break;
                                            k++;
                                            
                                        }
                                
                                    }

                            if(flag == false)
                                push(next,Open);              //把擴展點加入Open                         
                            
                    }

                }

             }
        
       }

       public void atFirstOpen() {          //把最小值放在Open表首位
           int indexmin=0;
           Node temp;
           Node node0 = (Node)Open.get(0);
           int minvalue = node0.f;
           
               for( int i = 0; i < Open.size(); i++ ) {
                   Node opei = (Node)Open.get(i);
                   if( opei.f < minvalue ) {
                       minvalue = opei.f;
                       indexmin = i;
                       
                   }
                   
               }
           
               temp = (Node)Open.get(0);
               Open.setElementAt( (Node)Open.elementAt(indexmin) , 0 );
               Open.setElementAt( temp , indexmin );
               
        }

        public Node found( int k , Vector vec , Node source ) {     //Close表中id相同的節(jié)點                   
            Node result = source;
            int i;
            
                for( i = 0; i < vec.size(); i++ ) {
                    if( k == ( (Node)vec.get(i) ).id ) {
                        result = (Node)vec.get(i);
                    }
                }
                    return result;
        }
        public static void main(String[] args){
            MACPS a = new MACPS();
            a.getSolutionStep();
        }
}