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