gistfile1.hpp

#include<iostream>

#define DEBUG

using namespace std;

class Boat{
//A graph vertex of the boat for cross river game.
 protected:
    bool iterated;
    int status[3];
    
 public:
    Boat *next[6]; // next status
	Boat *prev;    // recording prev status

    Boat(){
		Boat(0,0,0);
    }
    
    Boat(int m,int n,int b){
		iterated=false;
        setStatus(m,n,b);
		for(int i=0;i<5;i++) next[i]=NULL;
    }
    
    bool isSafe(){
        if(status[0]<status[1]) return false;
        if(status[0]<0 || status[1]<0) return false;
		if(status[0]>3 || status[1]>3) return false;
		if(this==prev) return false;
        return true;
    }
    
    bool setStatus(int m,int n,int b){
        status[0]=m;
        status[1]=n;
        status[2]=b;
        return isSafe();
    }
    
    int getStatus(int index){
        return status[index];
    }
};


void creatBoatStatusTree(Boat *boat){
 //All status in a boat (0,1) (1,0) (1,1) (0,2) (2,0)
	int ans=boat->getStatus(0) + boat->getStatus(1) + boat->getStatus(2);

    if ( !boat->isSafe() || ans==0 ){
         return ;
    }
	
    if(boat->getStatus(2)==1){
        boat->next[0]= new Boat(boat->getStatus(0)   ,boat->getStatus(1)-1  ,0);
        boat->next[1]= new Boat(boat->getStatus(0)-1 ,boat->getStatus(1)    ,0);
        boat->next[2]= new Boat(boat->getStatus(0)-1 ,boat->getStatus(1)-1  ,0);
        boat->next[3]= new Boat(boat->getStatus(0)   ,boat->getStatus(1)-2  ,0);
        boat->next[4]= new Boat(boat->getStatus(0)-2 ,boat->getStatus(1)    ,0);
		boat->next[0]->prev=boat;
		boat->next[1]->prev=boat;
		boat->next[2]->prev=boat;
		boat->next[3]->prev=boat;
		boat->next[4]->prev=boat;
	}else{
		boat->next[0]= new Boat(boat->getStatus(0)   ,boat->getStatus(1)+1  ,1);
        boat->next[1]= new Boat(boat->getStatus(0)+1 ,boat->getStatus(1)    ,1);
        boat->next[2]= new Boat(boat->getStatus(0)+1 ,boat->getStatus(1)+1  ,1);
        boat->next[3]= new Boat(boat->getStatus(0)   ,boat->getStatus(1)+2  ,1);
        boat->next[4]= new Boat(boat->getStatus(0)+2 ,boat->getStatus(1)    ,1);
		boat->next[0]->prev=boat;
		boat->next[1]->prev=boat;
		boat->next[2]->prev=boat;
		boat->next[3]->prev=boat;
		boat->next[4]->prev=boat;
	}
    
    //這段... /*
    creatBoatStatusTree(boat->next[0]);
    creatBoatStatusTree(boat->next[1]);
    creatBoatStatusTree(boat->next[2]);
    creatBoatStatusTree(boat->next[3]);
    creatBoatStatusTree(boat->next[4]);*/
}


void findSolutionRoute(Boat *boat){
   // do WFS
}


template <class Tree>
void printTreeDFS(Tree *node, int ident){
     if(!node->isSafe()) return;
     
     for(int i=0;i<ident;i++) cout << "--";
     cout << node->getStatus(0) ;
     cout << node->getStatus(1) ;
     cout << node->getStatus(2) << "\n";
     
     ident++;
     for(int i=0;i<5;i++){
         if(node->next[i] != NULL)
	         printTreeDFS(node->next[i], ident);
     }
}


int main(){
    Boat *boat=new Boat(3,3,1);
    creatBoatStatusTree(boat);
    //findSolutionRoute(boat);

#ifdef DEBUG
    boat->next[0]->next[0]= new Boat(0,0,0);
#endif

    printTreeDFS<Boat>(boat,0);
    system("pause");
    return 0;
}