fork download
copy 
  1. /**************************************************************************
  2.  
  3.    狼と山羊とキャベツと男 (幅優先探索)
  4.  
  5. **************************************************************************/
  6.  
  7. #include<stdio.h>
  8.  
  9. #include<stdlib.h>
  10.  
  11.  
  12.  
  13. #define MAN     0
  14.  
  15. #define WOLF    1
  16.  
  17. #define GOAT    2
  18.  
  19. #define CABBAGE 3
  20.  
  21.  
  22.  
  23. #define TimeMax 50
  24.  
  25.  
  26.  
  27. int state[TimeMax][5]; /* 男がいる側の状態  
  28.  
  29.                              state[t][4]が 0なら左岸 1なら右岸 */
  30.  
  31. int prev_state[TimeMax]; /* 過去の状態の履歴 */
  32.  
  33.  
  34.  
  35. /**************************************************************************
  36.  
  37.   状態の表示 
  38.  
  39.    引数 state[i] : 左岸もしくは右岸の状態
  40.  
  41.     state[i]の配列の内容に応じて状態を表示する
  42.  
  43.      (例) state[i]={1,1,1,1}ならば [ 男 狼 山羊 キャベツ ]
  44.  
  45.           state[i]={1,0,1,0}ならば [ 男 山羊 ]
  46.  
  47.           state[i]={0,0,0,0}ならば [  ]
  48.  
  49. **************************************************************************/
  50.  
  51. void print_state(int state[4]){
  52.  
  53.  
  54.  
  55.  /*** この部分を自分で作成する ***/
  56.  
  57.  
  58.  
  59. }
  60.  
  61.  
  62.  
  63. /**************************************************************************
  64.  
  65.   結果の表示 
  66.  
  67.    引数 t : ステップ数
  68.  
  69.      tステップ目の結果を表示する
  70.  
  71.       ステップ数: [ 左岸の状態 ] [ 右岸の状態 ]  
  72.  
  73.        (例) 0: [ 男 狼 山羊 キャベツ ] [ ] 
  74.  
  75.             1: [ 狼 山羊 ] [ 男 キャベツ ] 
  76.  
  77. **************************************************************************/
  78.  
  79. void print_ans(int t){
  80.  
  81.   int i;
  82.  
  83.   int right[4];
  84.  
  85.   int left[4];
  86.  
  87.  
  88.  
  89.   /* prev_state[t]に値が入っていれば状態を表示 */
  90.  
  91.   if(prev_state[t]!=-1){
  92.  
  93.     print_ans(prev_state[t]);
  94.  
  95.   }
  96.  
  97.  
  98.  
  99.   /* 男が右岸にいる場合 
  100.  
  101.        right[] に state[t][] をコピー & left[]のデータを生成 */
  102.  
  103.  
  104.  
  105.   /*** この部分を自分で作成する ***/
  106.  
  107.  
  108.  
  109.   /* 男が左岸にいる場合 
  110.  
  111.        left[] に state[t][] をコピー & right[]のデータを生成 */
  112.  
  113.  
  114.  
  115.   /*** この部分を自分で作成する ***/
  116.  
  117.  
  118.  
  119.   /* tステップの状態を表示する 
  120.  
  121.      [ヒント] print_state()の関数が正しく作成されていれば
  122.  
  123.                print_state(left_side[t]);  で tステップ目の左岸の状態、
  124.  
  125.                print_state(right_side[t]); で tステップ目の右岸の状態
  126.  
  127.               が表示できる */
  128.  
  129.  
  130.  
  131.   /*** この部分を自分で作成する ***/
  132.  
  133. }
  134.  
  135.  
  136.  
  137. /**************************************************************************
  138.  
  139.   状態のチェック
  140.  
  141.    引数 T : ステップ数
  142.  
  143.      ・狼と山羊、山羊とキャベツを残した状態でもなく、既に探索された状態
  144.  
  145.        でもなければ 1を返す
  146.  
  147.      ・それ以外は 0を返す
  148.  
  149. **************************************************************************/
  150.  
  151. int check_state(int T){
  152.  
  153.  
  154.  
  155.   int i,t;
  156.  
  157.   int now_state[4];   /* 男がいない側の現在の状態 */
  158.  
  159.   int count;
  160.  
  161.  
  162.  
  163.   /* 男がいない側の現在の状態をstate[T][]から生成し、now_state[]に代入 */
  164.  
  165.   /*** この部分を自分で作成する ***/
  166.  
  167.  
  168.  
  169.   /* 狼と山羊 もしくは 山羊とキャベツが一緒にないかをチェック
  170.  
  171.      あれば0を返す */
  172.  
  173.   /*** この部分を自分で作成する ***/
  174.  
  175.  
  176.  
  177.   /* 過去に同じ状態がないかをチェック  あれば0を返す
  178.  
  179.        [ヒント] state[t][i](tステップ目の状態)と
  180.  
  181.                 state[T][i](現在の状態)を比較してチェック */
  182.  
  183.   for(t=0;t<T;t++){
  184.  
  185.   /*** この部分を自分で作成する ***/
  186.  
  187.   }
  188.  
  189.  
  190.  
  191.   /* いずれにも該当しなければ1を返す */
  192.  
  193.   return 1;
  194.  
  195. }
  196.  
  197.  
  198.  
  199. /**************************************************************************
  200.  
  201.   幅優先探索
  202.  
  203. **************************************************************************/
  204.  
  205. void search(){
  206.  
  207.   int i,j;
  208.  
  209.   /*  r の位置にあるデータを取り出して、新しい状態を生成できたら、w の位置
  210.  
  211.       に書き込む */
  212.  
  213.   static int r=0; 
  214.  
  215.   static int w=1; 
  216.  
  217.  
  218.  
  219.   int now_state[5]; /* 男がいる側の現在の状態 */
  220.  
  221.   int new_state[5]; /* 次のステップの男がいる側の状態 */
  222.  
  223.  
  224.  
  225.   for(;r<w;r++){
  226.  
  227.     /* now_state[]に stage[r][]をコピー*/
  228.  
  229.     for(i=0;i<5;i++){
  230.  
  231.       now_state[i]=state[r][i];
  232.  
  233.     }
  234.  
  235.     for(i=0;i<4;i++){/* 0: 男 1: 狼 2: 山羊 3: キャベツ を順に調べる */
  236.  
  237.       if(now_state[i]==1){/* 移動できるのであれば(男と同じ側にいれば) */
  238.  
  239. 	/* iと男を移動(iが0の場合は男のみ移動)した後の状態を 
  240.  
  241. 	   new_state[]に格納 
  242.  
  243.           [ヒント] 現在の状態 (state[])をnew_state[]にコピーし,
  244.  
  245.                    iと男が移動した場合に値がどのように変化するかを設定 */
  246.  
  247.  
  248.  
  249. 	/*** この部分を自分で作成する ***/
  250.  
  251.  
  252.  
  253. 	/* state[w][]としてnew_state[]を保存 */
  254.  
  255.    	for(j=0;j<5;j++){
  256.  
  257. 	  state[w][j]=new_state[j];
  258.  
  259. 	}
  260.  
  261. 	/* prev_state[w]としてrを保存 */
  262.  
  263. 	prev_state[w]=r;
  264.  
  265. 	/* iと男を移動(iが0の場合は男のみ移動)した後の状態が有効かどうかを 
  266.  
  267.          チェック */
  268.  
  269. 	if(check_state(w)){
  270.  
  271. 	  /* 右岸にすべてが移動していれば 結果を表示して終了 */
  272.  
  273. 	  if(/*** この部分を自分で作成する ***/){
  274.  
  275. 	    print_ans(w);
  276.  
  277. 	  }
  278.  
  279. 	  w++;
  280.  
  281. 	}
  282.  
  283.       }
  284.  
  285.     }
  286.  
  287.   }
  288.  
  289. }
  290.  
  291.  
  292.  
  293. /**************************************************************************
  294.  
  295.   メインプログラム
  296.  
  297. **************************************************************************/
  298.  
  299. int main()
  300.  
  301. {
  302.  
  303.   int i,t;
  304.  
  305.  
  306.  
  307.   /* 初期化 */
  308.  
  309.   for(i=0;i<4;i++){
  310.  
  311.     state[0][i]=1; /* 最初はすべて左岸に(男と一緒に)いる */
  312.  
  313.   }
  314.  
  315.   state[0][4]=0; /* 男は左側にいるので0にセット */
  316.  
  317.  
  318.  
  319.   for(t=0;t<TimeMax;t++){
  320.  
  321.     prev_state[t]=-1;
  322.  
  323.   }
  324.  
  325.  
  326.  
  327.   /* 探索 */
  328.  
  329.   search();
  330.  
  331.  
  332.  
  333.   return 0;
  334.  
  335. }
  336.  
  337.  
  338.  
  339.  
  340.  
  341.  
  342.  
  343.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.c: In function ‘print_ans’:
prog.c:85: warning: unused variable ‘left’
prog.c:83: warning: unused variable ‘right’
prog.c:81: warning: unused variable ‘i’
prog.c: In function ‘check_state’:
prog.c:159: warning: unused variable ‘count’
prog.c:157: warning: unused variable ‘now_state’
prog.c:155: warning: unused variable ‘i’
prog.c: In function ‘search’:
prog.c:273: error: expected expression before ‘)’ token
stdout
copy 
Standard output is empty
https://ideone.com/9r5cn
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!