/**************************************************************************
   狼と山羊とキャベツと男 (幅優先探索)
**************************************************************************/
#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])
{
    /*** この部分を自分で作成する ***/
    static char *str[4] = { "男", "狼", "山羊", "キャベツ" };
    int i;

    printf("[ ");
    for(i = 0; i < 4; i++) {
        if(state[i] == 1) {
            printf("%s ", str[i]);
        }
    }
    printf(" ] ");
}

/**************************************************************************
  結果の表示 
   引数 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[]のデータを生成 */

    /*** この部分を自分で作成する ***/
    if(state[t][4] == 1) {
        for(i = 0; i < 4; i++) {
            right[i] = state[t][i];
            left[i] = 1 - state[t][i];  /* 0,1反転 */
        }
    }

    /* 男が左岸にいる場合 
       left[] に state[t][] をコピー & right[]のデータを生成 */

    /*** この部分を自分で作成する ***/
    else {
        for(i = 0; i < 4; i++) {
            left[i] = state[t][i];
            right[i] = 1 - state[t][i]; /* 0,1反転 */
        }
    }

    /* tステップの状態を表示する 
       [ヒント] print_state()の関数が正しく作成されていれば
       print_state(left_side[t]);  で tステップ目の左岸の状態、
       print_state(right_side[t]); で tステップ目の右岸の状態
       が表示できる */

    /*** この部分を自分で作成する ***/
    printf("%2d: ", t);
    print_state(left);
    print_state(right);
    printf("\n");
}

/**************************************************************************
  状態のチェック
   引数 T : ステップ数
     ・狼と山羊、山羊とキャベツを残した状態でもなく、既に探索された状態
       でもなければ 1を返す
     ・それ以外は 0を返す
**************************************************************************/
int check_state(int T)
{

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

    /* 男がいない側の現在の状態をstate[T][]から生成し、now_state[]に代入 */
    /*** この部分を自分で作成する ***/
    for(i = 0; i < 4; i++) {
        now_state[i] = 1 - state[T][i]; /* 0,1反転 */
    }

    /* 狼と山羊 もしくは 山羊とキャベツが一緒にないかをチェック
       あれば0を返す */
    /*** この部分を自分で作成する ***/
    if((now_state[WOLF] + now_state[GOAT] == 2)
       || (now_state[GOAT] + now_state[CABBAGE] == 2)) {
        return 0;
    }

    /* 過去に同じ状態がないかをチェック  あれば0を返す
       [ヒント] state[t][i](tステップ目の状態)と
       state[T][i](現在の状態)を比較してチェック */
    for(t = 0; t < T; t++) {
        /*** この部分を自分で作成する ***/
        for(i = 0; i < 5; i++) {
            if(state[t][i] != state[T][i]) {
                break;
            }
        }
        if(i == 5) {
            return 0;
        }
    }

    /* いずれにも該当しなければ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と男が移動した場合に値がどのように変化するかを設定 */

                /*** この部分を自分で作成する ***/
                for(j = 0; j < 5; j++) {
                    new_state[j] = 1 - now_state[j];    /* 0,1反転 */
                }
                new_state[MAN] = 1;
                new_state[i] = 1;

                /* 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( /*** この部分を自分で作成する ***/
                          (new_state[MAN] +
                           new_state[WOLF] +
                           new_state[GOAT] +
                           new_state[CABBAGE] + new_state[4]) == 5) {
                        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;
}