fork(15) download
copy 
  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.     i = 1;
  90.     while((t = prev_state[t]) != -1) {
  91.         i++;
  92.     }
  93.     printf("%2d: ", i);
  94.     print_state(left);
  95.     print_state(right);
  96.     printf("\n");
  97. }
  98.  
  99. /**************************************************************************
  100.   状態のチェック
  101.    引数 T : ステップ数
  102.      ・狼と山羊、山羊とキャベツを残した状態でもなく、既に探索された状態
  103.        でもなければ 1を返す
  104.      ・それ以外は 0を返す
  105. **************************************************************************/
  106. int check_state(int T)
  107. {
  108.  
  109.     int i, t;
  110.     int now_state[4];           /* 男がいない側の現在の状態 */
  111.     int count;
  112.  
  113.     /* 男がいない側の現在の状態をstate[T][]から生成し、now_state[]に代入 */
  114.     /*** この部分を自分で作成する ***/
  115.     for(i = 0; i < 4; i++) {
  116.         now_state[i] = 1 - state[T][i]; /* 0,1反転 */
  117.     }
  118.  
  119.     /* 狼と山羊 もしくは 山羊とキャベツが一緒にないかをチェック
  120.        あれば0を返す */
  121.     /*** この部分を自分で作成する ***/
  122.     if((now_state[WOLF] + now_state[GOAT] == 2)
  123.        || (now_state[GOAT] + now_state[CABBAGE] == 2)) {
  124.         return 0;
  125.     }
  126.  
  127.     /* 過去に同じ状態がないかをチェック  あれば0を返す
  128.        [ヒント] state[t][i](tステップ目の状態)と
  129.        state[T][i](現在の状態)を比較してチェック */
  130.     for(t = 0; t < T; t++) {
  131.         /*** この部分を自分で作成する ***/
  132.         for(i = 0; i < 5; i++) {
  133.             if(state[t][i] != state[T][i]) {
  134.                 break;
  135.             }
  136.         }
  137.         if(i == 5) {
  138.             return 0;
  139.         }
  140.     }
  141.  
  142.     /* いずれにも該当しなければ1を返す */
  143.     return 1;
  144. }
  145.  
  146. /**************************************************************************
  147.   幅優先探索
  148. **************************************************************************/
  149. void search()
  150. {
  151.     int i, j;
  152.  
  153.     /*  r の位置にあるデータを取り出して、新しい状態を生成できたら、w の位置
  154.        に書き込む */
  155.     static int r = 0;
  156.     static int w = 1;
  157.  
  158.     int now_state[5];           /* 男がいる側の現在の状態 */
  159.     int new_state[5];           /* 次のステップの男がいる側の状態 */
  160.  
  161.     for(; r < w; r++) {
  162.         /* now_state[]に stage[r][]をコピー */
  163.         for(i = 0; i < 5; i++) {
  164.             now_state[i] = state[r][i];
  165.         }
  166.         for(i = 0; i < 4; i++) {        /* 0: 男 1: 狼 2: 山羊 3: キャベツ を順に調べる */
  167.             if(now_state[i] == 1) {     /* 移動できるのであれば(男と同じ側にいれば) */
  168.                 /* iと男を移動(iが0の場合は男のみ移動)した後の状態を 
  169.                    new_state[]に格納 
  170.                    [ヒント] 現在の状態 (state[])をnew_state[]にコピーし,
  171.                    iと男が移動した場合に値がどのように変化するかを設定 */
  172.  
  173.                 /*** この部分を自分で作成する ***/
  174.                 for(j = 0; j < 5; j++) {
  175.                     new_state[j] = 1 - now_state[j];    /* 0,1反転 */
  176.                 }
  177.                 new_state[MAN] = 1;
  178.                 new_state[i] = 1;
  179.  
  180.                 /* state[w][]としてnew_state[]を保存 */
  181.                 for(j = 0; j < 5; j++) {
  182.                     state[w][j] = new_state[j];
  183.                 }
  184.                 /* prev_state[w]としてrを保存 */
  185.                 prev_state[w] = r;
  186.                 /* iと男を移動(iが0の場合は男のみ移動)した後の状態が有効かどうかを 
  187.                    チェック */
  188.                 if(check_state(w)) {
  189.                     /* 右岸にすべてが移動していれば 結果を表示して終了 */
  190.                     if( /*** この部分を自分で作成する ***/
  191.                           (new_state[MAN] +
  192.                            new_state[WOLF] +
  193.                            new_state[GOAT] +
  194.                            new_state[CABBAGE] + new_state[4]) == 5) {
  195.                         print_ans(w);
  196.                     }
  197.                     w++;
  198.                 }
  199.             }
  200.         }
  201.     }
  202. }
  203.  
  204. /**************************************************************************
  205.   メインプログラム
  206. **************************************************************************/
  207. int main()
  208. {
  209.     int i, t;
  210.  
  211.     /* 初期化 */
  212.     for(i = 0; i < 4; i++) {
  213.         state[0][i] = 1;        /* 最初はすべて左岸に(男と一緒に)いる */
  214.     }
  215.     state[0][4] = 0;            /* 男は左側にいるので0にセット */
  216.  
  217.     for(t = 0; t < TimeMax; t++) {
  218.         prev_state[t] = -1;
  219.     }
  220.  
  221.     /* 探索 */
  222.     search();
  223.  
  224.     return 0;
  225. }
  226.  
Success #stdin #stdout 0.01s 1720KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
 1: [ 男 狼 山羊 キャベツ  ] [  ] 
 2: [ 狼 キャベツ  ] [ 男 山羊  ] 
 3: [ 男 狼 キャベツ  ] [ 山羊  ] 
 4: [ キャベツ  ] [ 男 狼 山羊  ] 
 5: [ 男 山羊 キャベツ  ] [ 狼  ] 
 6: [ 山羊  ] [ 男 狼 キャベツ  ] 
 7: [ 男 山羊  ] [ 狼 キャベツ  ] 
 8: [  ] [ 男 狼 山羊 キャベツ  ]
https://ideone.com/F20Gh
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!