fork(1) 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 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.  
  29. }
  30.  
  31. /**************************************************************************
  32.   結果の表示 
  33.    引数 T : ステップ数
  34.      Tステップ目までの結果を表示する
  35.       ステップ数: [ 左岸の状態 ] [ 右岸の状態 ]  
  36.        (例) 0: [ 男 狼 山羊 キャベツ ] [ ] 
  37.             1: [ 狼 山羊 ] [ 男 キャベツ ] 
  38. **************************************************************************/
  39. void print_ans(int T)
  40. {
  41.   int t;
  42.  
  43.   /* 初期状態からTステップ目までの結果を表示する 
  44.      [ヒント] print_state()の関数が正しく作成されていれば
  45.                print_state(left_side[t]);  で tステップ目の左岸の状態、
  46.                print_state(right_side[t]); で tステップ目の右岸の状態
  47.               が表示できる */
  48.  
  49.   for(t=0;t<=T;t++){
  50.   /*** この部分を自分で作成する ***/
  51.   }
  52. }
  53.  
  54. /**************************************************************************
  55.   状態のチェック
  56.    引数 T                 : ステップ数
  57.         state[i]          : チェックしたい状態
  58.         past_state[t][i]  : 過去の状態(tステップ目の状態)
  59.      ・狼と山羊、山羊とキャベツを残した状態でもなく、既に探索された状態
  60.        でもなければ 1を返す
  61.      ・それ以外は 0を返す
  62. **************************************************************************/
  63. int check_state(int T,int state[4], int past_state[SearchMax][4]){
  64.   int i,t;
  65.   int count;
  66.  
  67.   /* 狼と山羊 もしくは 山羊とキャベツが一緒にないかをチェック
  68.      あれば0を返す */
  69.  
  70.   /*** この部分を自分で作成する ***/
  71.  
  72.   /* 過去に同じ状態がないかをチェック  あれば0を返す
  73.        [ヒント] past_state[t][i](tステップ目の状態)と
  74.                 state[i](現在の状態)を比較してチェック */
  75.   for(t=0;t<T;t++){
  76.   /*** この部分を自分で作成する ***/
  77.   }  
  78.   /* いずれにも該当しなければ1を返す */
  79.   return 1;
  80. }
  81.  
  82. /**************************************************************************
  83.   深さ優先探索
  84.    引数 T                 : ステップ数
  85.         src_side[t][i]    : 男がいる側の状態  
  86.         dest_side[t][i]   : 男がいない側の状態
  87. **************************************************************************/
  88. void search(int T, int src_side[SearchMax][4], int dest_side[SearchMax][4]){
  89.   int i,j;
  90.  
  91.   int src_state[4];      /* 男がいる側の状態 */
  92.   int dest_state[4];     /* 男がいない側の状態 */
  93.   int new_src_state[4];  /* 男がいる側の次のステップの状態 */
  94.   int new_dest_state[4]; /* 男がいない側の次のステップでの状態 */
  95.  
  96.   /* Tステップ目の状態をコピー */
  97.   for(i=0;i<4;i++){
  98.     src_state[i]=src_side[T][i];
  99.     dest_state[i]=dest_side[T][i];
  100.   }
  101.  
  102.   for(i=0;i<4;i++){ /* 0: 男 1: 狼 2: 山羊 3: キャベツ を順に調べる */
  103.     if(src_state[i]==1){ /* 移動できるのであれば(男と同じ側にいるのであれば) */
  104.       /* iと男を移動(iが0の場合は男のみ移動)した後の状態を 
  105.          new_src_state[], new_dest_state[] に格納 
  106.           [ヒント] 現在の状態 (src_state[], dest_state[])を
  107.                    new_src_state[], new_dest_state[]にコピーし,
  108.                    iと男が移動した場合に値がどのように変化するかを設定 */
  109.  
  110.       /*** この部分を自分で作成する ***/
  111.  
  112.       /* iと男を移動(iが0の場合は男のみ移動)した後の状態が有効かどうかを 
  113.          チェックし、有効であれば 岸の状態を更新し、次に進む */
  114.       if(check_state(T,new_src_state,src_side)){
  115. 	/* 男が左岸にいる場合(Tが偶数の場合) 
  116. 	   left_side[T+1][]に new_src_state[]をコピー 
  117. 	   right_side[T+1][]に new_dest_state[]をコピー */
  118. 	if(T%2==0){
  119.           /*** この部分を自分で作成する ***/
  120. 	}
  121. 	/* 男が右岸にいる場合(Tが奇数の場合) 
  122. 	   right_side[T+1][]に new_src_state[]をコピー 
  123. 	   left_side[T+1][]に new_dest_state[]をコピー */
  124. 	else{
  125.           /*** この部分を自分で作成する ***/
  126. 	}
  127. 	/* 右岸にすべてが移動していれば 結果を表示して終了 */
  128. 	if(/*** この部分を自分で作成する ***/){
  129. 	  print_ans(T+1);
  130. 	   exit(0);
  131. 	}
  132. 	/* そうでなければ再帰的に探索を続ける */
  133. 	else{
  134. 	  search(T+1,dest_side,src_side);
  135. 	}
  136.       }
  137.     }
  138.   }
  139. }
  140.  
  141. /**************************************************************************
  142.   メインプログラム
  143. **************************************************************************/
  144. int main()
  145. {
  146.   int i,t;
  147.  
  148.   /* 配列の初期化 (-1を設定) */
  149.   for(t=0;t<SearchMax;t++){
  150.     for(i=0;i<4;i++){
  151.       left_side[t][i]=-1;
  152.       right_side[t][i]=-1;
  153.     }
  154.   }
  155.  
  156.   /* 初期状態の設定 */
  157.   for(i=0;i<4;i++){
  158.     left_side[0][i]=1;
  159.     right_side[0][i]=0;
  160.   }
  161.  
  162.   /* 探索 */
  163.   search(0,left_side,right_side);
  164.  
  165.   return 0;
  166. }
  167.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
prog.c: In function ‘check_state’:
prog.c:65: warning: unused variable ‘count’
prog.c:64: warning: unused variable ‘i’
prog.c: In function ‘search’:
prog.c:128: error: expected expression before ‘)’ token
prog.c:94: warning: unused variable ‘new_dest_state’
prog.c:89: warning: unused variable ‘j’
stdout 
Standard output is empty
https://ideone.com/E3ZL6
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!