/**************************************************************************

   狼と山羊とキャベツと男 (幅優先探索)

**************************************************************************/

#include<stdio.h>

#include<stdlib.h>



#define MAN     0

#define WOLF    1

#define GOAT    2

#define CABBAGE 3



#define TimeMax 50



int state[TimeMax][5]; /* 男がいる側の状態  

                             state[t][4]が 0なら左岸 1なら右岸 */

int prev_state[TimeMax]; /* 過去の状態の履歴 */



/**************************************************************************

  状態の表示 

   引数 state[i] : 左岸もしくは右岸の状態

    state[i]の配列の内容に応じて状態を表示する

     (例) state[i]={1,1,1,1}ならば [ 男 狼 山羊 キャベツ ]

          state[i]={1,0,1,0}ならば [ 男 山羊 ]

          state[i]={0,0,0,0}ならば [  ]

**************************************************************************/

void print_state(int state[4]){



 /*** この部分を自分で作成する ***/



}



/**************************************************************************

  結果の表示 

   引数 t : ステップ数

     tステップ目の結果を表示する

      ステップ数: [ 左岸の状態 ] [ 右岸の状態 ]  

       (例) 0: [ 男 狼 山羊 キャベツ ] [ ] 

            1: [ 狼 山羊 ] [ 男 キャベツ ] 

**************************************************************************/

void print_ans(int t){

  int i;

  int right[4];

  int left[4];



  /* prev_state[t]に値が入っていれば状態を表示 */

  if(prev_state[t]!=-1){

    print_ans(prev_state[t]);

  }



  /* 男が右岸にいる場合 

       right[] に state[t][] をコピー & left[]のデータを生成 */



  /*** この部分を自分で作成する ***/



  /* 男が左岸にいる場合 

       left[] に state[t][] をコピー & right[]のデータを生成 */

  

  /*** この部分を自分で作成する ***/



  /* tステップの状態を表示する 

     [ヒント] print_state()の関数が正しく作成されていれば

               print_state(left_side[t]);  で tステップ目の左岸の状態、

               print_state(right_side[t]); で tステップ目の右岸の状態

              が表示できる */



  /*** この部分を自分で作成する ***/

}



/**************************************************************************

  状態のチェック

   引数 T : ステップ数

     ・狼と山羊、山羊とキャベツを残した状態でもなく、既に探索された状態

       でもなければ 1を返す

     ・それ以外は 0を返す

**************************************************************************/

int check_state(int T){



  int i,t;

  int now_state[4];   /* 男がいない側の現在の状態 */

  int count;



  /* 男がいない側の現在の状態をstate[T][]から生成し、now_state[]に代入 */

  /*** この部分を自分で作成する ***/



  /* 狼と山羊 もしくは 山羊とキャベツが一緒にないかをチェック

     あれば0を返す */

  /*** この部分を自分で作成する ***/



  /* 過去に同じ状態がないかをチェック  あれば0を返す

       [ヒント] state[t][i](tステップ目の状態)と

                state[T][i](現在の状態)を比較してチェック */

  for(t=0;t<T;t++){

  /*** この部分を自分で作成する ***/

  }



  /* いずれにも該当しなければ1を返す */

  return 1;

}



/**************************************************************************

  幅優先探索

**************************************************************************/

void search(){

  int i,j;

  /*  r の位置にあるデータを取り出して、新しい状態を生成できたら、w の位置

      に書き込む */

  static int r=0; 

  static int w=1; 



  int now_state[5]; /* 男がいる側の現在の状態 */

  int new_state[5]; /* 次のステップの男がいる側の状態 */



  for(;r<w;r++){

    /* now_state[]に stage[r][]をコピー*/

    for(i=0;i<5;i++){

      now_state[i]=state[r][i];

    }

    for(i=0;i<4;i++){/* 0: 男 1: 狼 2: 山羊 3: キャベツ を順に調べる */

      if(now_state[i]==1){/* 移動できるのであれば(男と同じ側にいれば) */

	/* iと男を移動(iが0の場合は男のみ移動)した後の状態を 

	   new_state[]に格納 

          [ヒント] 現在の状態 (state[])をnew_state[]にコピーし,

                   iと男が移動した場合に値がどのように変化するかを設定 */



	/*** この部分を自分で作成する ***/



	/* state[w][]としてnew_state[]を保存 */

   	for(j=0;j<5;j++){

	  state[w][j]=new_state[j];

	}

	/* prev_state[w]としてrを保存 */

	prev_state[w]=r;

	/* iと男を移動(iが0の場合は男のみ移動)した後の状態が有効かどうかを 

         チェック */

	if(check_state(w)){

	  /* 右岸にすべてが移動していれば 結果を表示して終了 */

	  if(/*** この部分を自分で作成する ***/){

	    print_ans(w);

	  }

	  w++;

	}

      }

    }

  }

}



/**************************************************************************

  メインプログラム

**************************************************************************/

int main()

{

  int i,t;



  /* 初期化 */

  for(i=0;i<4;i++){

    state[0][i]=1; /* 最初はすべて左岸に(男と一緒に)いる */

  }

  state[0][4]=0; /* 男は左側にいるので0にセット */



  for(t=0;t<TimeMax;t++){

    prev_state[t]=-1;

  }



  /* 探索 */

  search();



  return 0;

}