fork(10) download 
  1. /**************************************************************************
  2.    狼と山羊とキャベツと男 (幅優先探索)
  3. **************************************************************************/
  4. #include<stdio.h>
  5. #include<stdlib.h>
  6.  
  7. #define MAN     0
  8. #define WOLF    1
  9. #define GOAT    2
  10. #define CABBAGE 3
  11.  
  12. #define TimeMax 50
  13.  
  14. int state[TimeMax][5];          /* 男がいる側の状態  
  15.                                    state[t][4]が 0なら左岸 1なら右岸 */
  16. int prev_state[TimeMax];        /* 過去の状態の履歴 */
  17.  
  18. /**************************************************************************
  19.   状態の表示 
  20.    引数 state[i] : 左岸もしくは右岸の状態
  21.     state[i]の配列の内容に応じて状態を表示する
  22.      (例) state[i]={1,1,1,1}ならば [ 男 狼 山羊 キャベツ ]
  23.           state[i]={1,0,1,0}ならば [ 男 山羊 ]
  24.           state[i]={0,0,0,0}ならば [  ]
  25. **************************************************************************/
  26. void print_state(int state[4])
  27. {
  28.     /*** この部分を自分で作成する ***/
  29.     static char *str[4] = { "男", "狼", "山羊", "キャベツ" };
  30.     int i;
  31.  
  32.     printf("[ ");
  33.     for(i = 0; i < 4; i++) {
  34.         if(state[i] == 1) {
  35.             printf("%s ", str[i]);
  36.         }
  37.     }
  38.     printf(" ] ");
  39. }
  40.  
  41. /**************************************************************************
  42.   結果の表示 
  43.    引数 t : ステップ数
  44.      tステップ目の結果を表示する
  45.       ステップ数: [ 左岸の状態 ] [ 右岸の状態 ]  
  46.        (例) 0: [ 男 狼 山羊 キャベツ ] [ ] 
  47.             1: [ 狼 山羊 ] [ 男 キャベツ ] 
  48. **************************************************************************/
  49. void print_ans(int t)
  50. {
  51.     int i;
  52.     int right[4];
  53.     int left[4];
  54.  
  55.     /* prev_state[t]に値が入っていれば状態を表示 */
  56.     if(prev_state[t] != -1) {
  57.         print_ans(prev_state[t]);
  58.     }
  59.  
  60.     /* 男が右岸にいる場合 
  61.        right[] に state[t][] をコピー & left[]のデータを生成 */
  62.  
  63.     /*** この部分を自分で作成する ***/
  64.     if(state[t][4] == 1) {
  65.         for(i = 0; i < 4; i++) {
  66.             right[i] = state[t][i];
  67.             left[i] = 1 - state[t][i];  /* 0,1反転 */
  68.         }
  69.     }
  70.  
  71.     /* 男が左岸にいる場合 
  72.        left[] に state[t][] をコピー & right[]のデータを生成 */
  73.  
  74.     /*** この部分を自分で作成する ***/
  75.     else {
  76.         for(i = 0; i < 4; i++) {
  77.             left[i] = state[t][i];
  78.             right[i] = 1 - state[t][i]; /* 0,1反転 */
  79.         }
  80.     }
  81.  
  82.     /* tステップの状態を表示する 
  83.        [ヒント] print_state()の関数が正しく作成されていれば
  84.        print_state(left_side[t]);  で tステップ目の左岸の状態、
  85.        print_state(right_side[t]); で tステップ目の右岸の状態
  86.        が表示できる */
  87.  
  88.     /*** この部分を自分で作成する ***/
  89.     printf("%2d: ", t);
  90.     print_state(left);
  91.     print_state(right);
  92.     printf("\n");
  93. }
  94.  
  95. /**************************************************************************
  96.   状態のチェック
  97.    引数 T : ステップ数
  98.      ・狼と山羊、山羊とキャベツを残した状態でもなく、既に探索された状態
  99.        でもなければ 1を返す
  100.      ・それ以外は 0を返す
  101. **************************************************************************/
  102. int check_state(int T)
  103. {
  104.  
  105.     int i, t;
  106.     int now_state[4];           /* 男がいない側の現在の状態 */
  107.     int count;
  108.  
  109.     /* 男がいない側の現在の状態をstate[T][]から生成し、now_state[]に代入 */
  110.     /*** この部分を自分で作成する ***/
  111.     for(i = 0; i < 4; i++) {
  112.         now_state[i] = 1 - state[T][i]; /* 0,1反転 */
  113.     }
  114.  
  115.     /* 狼と山羊 もしくは 山羊とキャベツが一緒にないかをチェック
  116.        あれば0を返す */
  117.     /*** この部分を自分で作成する ***/
  118.     if((now_state[WOLF] + now_state[GOAT] == 2)
  119.        || (now_state[GOAT] + now_state[CABBAGE] == 2)) {
  120.         return 0;
  121.     }
  122.  
  123.     /* 過去に同じ状態がないかをチェック  あれば0を返す
  124.        [ヒント] state[t][i](tステップ目の状態)と
  125.        state[T][i](現在の状態)を比較してチェック */
  126.     for(t = 0; t < T; t++) {
  127.         /*** この部分を自分で作成する ***/
  128.         for(i = 0; i < 5; i++) {
  129.             if(state[t][i] != state[T][i]) {
  130.                 break;
  131.             }
  132.         }
  133.         if(i == 5) {
  134.             return 0;
  135.         }
  136.     }
  137.  
  138.     /* いずれにも該当しなければ1を返す */
  139.     return 1;
  140. }
  141.  
  142. /**************************************************************************
  143.   幅優先探索
  144. **************************************************************************/
  145. void search()
  146. {
  147.     int i, j;
  148.  
  149.     /*  r の位置にあるデータを取り出して、新しい状態を生成できたら、w の位置
  150.        に書き込む */
  151.     static int r = 0;
  152.     static int w = 1;
  153.  
  154.     int now_state[5];           /* 男がいる側の現在の状態 */
  155.     int new_state[5];           /* 次のステップの男がいる側の状態 */
  156.  
  157.     for(; r < w; r++) {
  158.         /* now_state[]に stage[r][]をコピー */
  159.         for(i = 0; i < 5; i++) {
  160.             now_state[i] = state[r][i];
  161.         }
  162.         for(i = 0; i < 4; i++) {        /* 0: 男 1: 狼 2: 山羊 3: キャベツ を順に調べる */
  163.             if(now_state[i] == 1) {     /* 移動できるのであれば(男と同じ側にいれば) */
  164.                 /* iと男を移動(iが0の場合は男のみ移動)した後の状態を 
  165.                    new_state[]に格納 
  166.                    [ヒント] 現在の状態 (state[])をnew_state[]にコピーし,
  167.                    iと男が移動した場合に値がどのように変化するかを設定 */
  168.  
  169.                 /*** この部分を自分で作成する ***/
  170.                 for(j = 0; j < 5; j++) {
  171.                     new_state[j] = 1 - now_state[j];    /* 0,1反転 */
  172.                 }
  173.                 new_state[MAN] = 1;
  174.                 new_state[i] = 1;
  175.  
  176.                 /* state[w][]としてnew_state[]を保存 */
  177.                 for(j = 0; j < 5; j++) {
  178.                     state[w][j] = new_state[j];
  179.                 }
  180.                 /* prev_state[w]としてrを保存 */
  181.                 prev_state[w] = r;
  182.                 /* iと男を移動(iが0の場合は男のみ移動)した後の状態が有効かどうかを 
  183.                    チェック */
  184.                 if(check_state(w)) {
  185.                     /* 右岸にすべてが移動していれば 結果を表示して終了 */
  186.                     if( /*** この部分を自分で作成する ***/
  187.                           (new_state[MAN] +
  188.                            new_state[WOLF] +
  189.                            new_state[GOAT] +
  190.                            new_state[CABBAGE] + new_state[4]) == 5) {
  191.                         print_ans(w);
  192.                     }
  193.                     w++;
  194.                 }
  195.             }
  196.         }
  197.     }
  198. }
  199.  
  200. /**************************************************************************
  201.   メインプログラム
  202. **************************************************************************/
  203. int main()
  204. {
  205.     int i, t;
  206.  
  207.     /* 初期化 */
  208.     for(i = 0; i < 4; i++) {
  209.         state[0][i] = 1;        /* 最初はすべて左岸に(男と一緒に)いる */
  210.     }
  211.     state[0][4] = 0;            /* 男は左側にいるので0にセット */
  212.  
  213.     for(t = 0; t < TimeMax; t++) {
  214.         prev_state[t] = -1;
  215.     }
  216.  
  217.     /* 探索 */
  218.     search();
  219.  
  220.     return 0;
  221. }
  222.  
Success #stdin #stdout 0.02s 1720KB
comments (?)
stdin 
Standard input is empty
stdout 
 0: [ 男 狼 山羊 キャベツ  ] [  ] 
 1: [ 狼 キャベツ  ] [ 男 山羊  ] 
 2: [ 男 狼 キャベツ  ] [ 山羊  ] 
 3: [ キャベツ  ] [ 男 狼 山羊  ] 
 5: [ 男 山羊 キャベツ  ] [ 狼  ] 
 7: [ 山羊  ] [ 男 狼 キャベツ  ] 
 8: [ 男 山羊  ] [ 狼 キャベツ  ] 
 9: [  ] [ 男 狼 山羊 キャベツ  ]
https://ideone.com/D6KUc
language:
C (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!