fork(1) download
copy 
  1. // include
  2. #include <algorithm>
  3. #include <sstream>
  4. #include <queue>
  5. #include <iostream>
  6. #include <cmath>
  7. #include <string>
  8.  
  9. using namespace std;
  10.  
  11. // 数値を文字列に変換する
  12. template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
  13.  
  14. // repetition
  15. #define FOR(i,a,b) for(int i=(a);i<(b);i++)
  16. #define REP(i,n) FOR(i,0,n)
  17.  
  18. const int Target     = 4; // 目的の値
  19. const int PitcherNum = 3;  // ピッチャーの数
  20. const int PitcherMax[PitcherNum] = {8, 5, 3}; // 各ピッチャーの最大値
  21.  
  22. // 終了条件を満たすか調べる
  23. bool check(int *Pitchers)
  24. {
  25.     REP(i, PitcherNum)
  26.         if (Pitchers[i] == Target) return true;
  27.     return false;
  28. }
  29.  
  30. // 現在の状態を保持する構造体
  31. struct Status
  32. {
  33.     int p[3];
  34.     int cnt;
  35.     string ret;
  36. };
  37.  
  38. // 幅優先で解く
  39. Status SolveBFS()
  40. {
  41.     bool flag[PitcherMax[0]+1][PitcherMax[1]+1][PitcherMax[2]+1]; // ある状態になった事があるかを保持する（この処理がないと無限ループ）
  42.  
  43.     // 配列の初期化
  44.     REP(i, PitcherMax[0]+1)
  45.         REP(j, PitcherMax[1]+1)
  46.             REP(k, PitcherMax[2]+1)
  47.                 flag[i][j][k] = false;
  48.  
  49.     queue<Status> bfs; // 幅優先用のキュー
  50.  
  51.     Status state;
  52.     state.p[0] = PitcherMax[0];
  53.     state.p[1] = 0;
  54.     state.p[2] = 0;
  55.     state.cnt = 0;
  56.     state.ret = toString(state.p[0]) + " " + toString(state.p[1]) + " " + toString(state.p[2]) + "\n";
  57.     bfs.push(state); // 初期状態をキューに追加
  58.  
  59.     while (!bfs.empty()) // キューが空になるまでループ
  60.     {
  61.         state = bfs.front(); bfs.pop(); // キューの先頭から要素を一つ取り出す
  62.         if (check(state.p)) break; // 終了条件を満たしていれば終わる
  63.         if (flag[state.p[0]][state.p[1]][state.p[2]]) continue; // 訪れたことがあるならスキップ
  64.         else flag[state.p[0]][state.p[1]][state.p[2]] = true; // 訪れたことがないなら、フラグを立てる
  65.  
  66.         Status newState; // 次の状態
  67.         REP (i, PitcherNum)
  68.         {
  69.             REP (j, PitcherNum)
  70.             {
  71.                 if (i == j) continue; // 同じピッチャーに移すことはないからスキップ (例：８のピッチャー -> ８のピッチャー)
  72.  
  73.                 // 中身を移す処理
  74.                 newState.p[i] = max(state.p[i] - (PitcherMax[j] - state.p[j]), 0);
  75.                 newState.p[j] = min(state.p[j] + state.p[i], PitcherMax[j]);
  76.                 newState.p[3 - i - j] = state.p[3 - i - j];
  77.  
  78.                 // 移動した回数を1増やす
  79.                 newState.cnt = state.cnt + 1;
  80.  
  81.                 // ピッチャーの状態遷移をメモする
  82.                 newState.ret = state.ret + toString(newState.p[0]) + " " + toString(newState.p[1]) + " " + toString(newState.p[2]) + "\n";
  83.  
  84.                 // ピッチャーの中身が移動していない場合はスキップする
  85.                 if (newState.p[i] == state.p[i]) continue;
  86.  
  87.                 // キューに状態を追加
  88.                 bfs.push(newState);
  89.             }
  90.         }
  91.     }
  92.     if (check(state.p)) return state;
  93.     else
  94.     {
  95.         state.cnt = -1;
  96.         state.ret = "目的の値になりませんでした";
  97.         return state;
  98.     }
  99. }
  100.  
  101. int main()
  102. {
  103.     Status result = SolveBFS();
  104.  
  105.     cout << "目的の値: " << Target << endl;
  106.     cout << "移動回数: " << result.cnt << endl;
  107.     cout << "ピッチャーの状態遷移:" << endl;
  108.     cout << result.ret << endl;
  109.  
  110.     return 0;
  111. }
  112.  
Success #stdin #stdout 0s 3428KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
目的の値: 4
移動回数: 6
ピッチャーの状態遷移:
8 0 0
3 5 0
3 2 3
6 2 0
6 0 2
1 5 2
1 4 3
https://ideone.com/2Wk0wT
WaterJugProblem Solve with BFS
language:
C++14 (gcc 8.3)
created:
8 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!