Advertisement
Guest User

Untitled

a guest
Oct 8th, 2016
401
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.99 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4.  
  5. using namespace std;
  6.  
  7. vector < short > clockk;
  8.  
  9. bool check(vector < short > c)
  10. {
  11. for (int i = 0; i < 9; i++) {
  12. if (c[i] != 0)return false;
  13. }
  14. return true;
  15. }
  16.  
  17. pair < vector < short >, vector < short > > change(pair < vector < short >, vector < short > > temp, int num)
  18. {
  19. if (num == 0) {
  20. temp.first[0] += 3;
  21. temp.first[1] += 3;
  22. temp.first[3] += 3;
  23. temp.first[4] += 3;
  24. temp.first[0] %= 12;
  25. temp.first[1] %= 12;
  26. temp.first[2] %= 12;
  27. temp.first[4] %= 12;
  28. return temp;
  29. }
  30. if (num == 1) {
  31. temp.first[0] += 3;
  32. temp.first[1] += 3;
  33. temp.first[2] += 3;
  34. temp.first[0] %= 12;
  35. temp.first[1] %= 12;
  36. temp.first[2] %= 12;
  37. return temp;
  38. }
  39. if (num == 2) {
  40. temp.first[1] += 3;
  41. temp.first[2] += 3;
  42. temp.first[4] += 3;
  43. temp.first[5] += 3;
  44. temp.first[1] %= 12;
  45. temp.first[2] %= 12;
  46. temp.first[4] %= 12;
  47. temp.first[5] %= 12;
  48. return temp;
  49. }
  50. if (num == 3) {
  51. temp.first[0] += 3;
  52. temp.first[3] += 3;
  53. temp.first[6] += 3;
  54. temp.first[0] %= 12;
  55. temp.first[3] %= 12;
  56. temp.first[6] %= 12;
  57. return temp;
  58. }
  59. if (num == 4) {
  60. temp.first[1] += 3;
  61. temp.first[3] += 3;
  62. temp.first[4] += 3;
  63. temp.first[5] += 3;
  64. temp.first[7] += 3;
  65. temp.first[1] %= 12;
  66. temp.first[3] %= 12;
  67. temp.first[4] %= 12;
  68. temp.first[5] %= 12;
  69. temp.first[7] %= 12;
  70. return temp;
  71. }
  72. if (num == 5) {
  73. temp.first[2] += 3;
  74. temp.first[5] += 3;
  75. temp.first[8] += 3;
  76. temp.first[2] %= 12;
  77. temp.first[5] %= 12;
  78. temp.first[8] %= 12;
  79. return temp;
  80. }
  81. if (num == 6) {
  82. temp.first[3] += 3;
  83. temp.first[4] += 3;
  84. temp.first[6] += 3;
  85. temp.first[7] += 3;
  86. temp.first[3] %= 12;
  87. temp.first[4] %= 12;
  88. temp.first[6] %= 12;
  89. temp.first[7] %= 12;
  90. return temp;
  91. }
  92. if (num == 7) {
  93. temp.first[6] += 3;
  94. temp.first[7] += 3;
  95. temp.first[8] += 3;
  96. temp.first[6] %= 12;
  97. temp.first[7] %= 12;
  98. temp.first[8] %= 12;
  99. return temp;
  100. }
  101. if (num == 8) {
  102. temp.first[4] += 3;
  103. temp.first[5] += 3;
  104. temp.first[7] += 3;
  105. temp.first[8] += 3;
  106. temp.first[4] %= 12;
  107. temp.first[5] %= 12;
  108. temp.first[7] %= 12;
  109. temp.first[8] %= 12;
  110. return temp;
  111. }
  112. }
  113.  
  114. void BFS()
  115. {
  116. queue < pair < vector < short >, vector < short > > > q;
  117. vector < short > temp;
  118. for (int i = 0; i < 9; i++)
  119. temp.push_back(0);
  120. q.push({clockk, temp});
  121. while (!q.empty()) {
  122. pair < vector < short >, vector < short > > u = q.front();
  123. q.pop();
  124. if (check(u.first)) {
  125. for (int i = 0; i < 9; i++) {
  126. while (u.second[i]--) {
  127. cout << i + 1 << ' ';
  128. }
  129. }
  130. return;
  131. }
  132. if (q.size() < 10000) {
  133. for (int i = 0; i < 9; i++) {
  134. if (u.second[i] < 3) {
  135. pair < vector < short >, vector < short > > v = u;
  136. u.second[i]++;
  137. u = change(u, i);
  138. q.push(u);
  139. u = v;
  140. }
  141. }
  142. }
  143. }
  144. }
  145.  
  146.  
  147. int main()
  148. {
  149. short num;
  150. for (int i = 0; i < 9; i++) {
  151. cin >> num;
  152. num %= 12;
  153. clockk.push_back(num);
  154. }
  155. BFS();
  156. return 0;
  157. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement