Advertisement
Derga

Untitled

Jun 18th, 2024
398
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.51 KB | None | 0 0
  1. #include <iostream>
  2. #include <map>
  3. #include <string>
  4. #include <queue>
  5. #include <vector>
  6.  
  7. using namespace std;
  8.  
  9. /*
  10. точками изображена часть кубика, которую не видно
  11.  
  12.    ________
  13.   /⠡      /\
  14.  /  ⠡ U B/  \
  15. /____⠡__/....\
  16. \  L ⠌ D\ R  /
  17.  \  ⠌ F  \  /
  18.   \⠌______\/
  19.  
  20. */
  21.  
  22.  
  23. //6 граней
  24. //передняя (F), левая (L), задняя (B), правая (R), верхняя (U) и нижняя (D)
  25. const vector<char> FACES = { 'F', 'L','B','R','U','D' };
  26. const int BACK = -1;
  27. const int FORWARD = 1;
  28.  
  29. struct RubiksCube {
  30.     RubiksCube() : faces_dates(26, vector<vector<char>>(2, vector<char>(2))) {}
  31.  
  32.     bool IsSolved() const {
  33.         for (const auto& face_date : faces_dates) {
  34.             char value = face_date.front().front();
  35.             for (const auto& row : face_date) {
  36.                 for (char c : row) {
  37.                     if (c != value) return false;
  38.                 }
  39.             }
  40.         }
  41.         return true;
  42.     }
  43.  
  44.     void RotateFaceForward(char face) {
  45.         char save_front_front = faces_dates[face - 'A'].front().front();
  46.         faces_dates[face - 'A'].front().front() = faces_dates[face - 'A'].back().front();
  47.         faces_dates[face - 'A'].back().front()  = faces_dates[face - 'A'].back().back();
  48.         faces_dates[face - 'A'].back().back()   = faces_dates[face - 'A'].front().back();
  49.         faces_dates[face - 'A'].front().back()  = save_front_front;
  50.     }
  51.  
  52.     void RotateFaceBack(char face) {
  53.         char save_front_front = faces_dates[face - 'A'].front().front();
  54.         faces_dates[face - 'A'].front().front() = faces_dates[face - 'A'].front().back();
  55.         faces_dates[face - 'A'].front().back() = faces_dates[face - 'A'].back().back();
  56.         faces_dates[face - 'A'].back().back() = faces_dates[face - 'A'].back().front();
  57.         faces_dates[face - 'A'].back().front() = save_front_front;
  58.     }
  59.  
  60.     void DoRotate(char face, int direction) {
  61.         if (direction == FORWARD) {
  62.             //передняя (F), левая (L), задняя (B), правая (R), верхняя (U) и нижняя (D)
  63.             if (face == 'R' || face == 'L') {
  64.                 char save_upper_right_F = faces_dates['F' - 'A'].front().back();
  65.                 char save_lower_right_F = faces_dates['F' - 'A'].back().back();
  66.  
  67.                 faces_dates['F' - 'A'].front().back() = faces_dates['D' - 'A'].front().back();
  68.                 faces_dates['F' - 'A'].back().back()  = faces_dates['D' - 'A'].back().back();
  69.  
  70.                 faces_dates['D' - 'A'].front().back() = faces_dates['B' - 'A'].front().back();
  71.                 faces_dates['D' - 'A'].back().back()  = faces_dates['B' - 'A'].back().back();
  72.  
  73.                 faces_dates['B' - 'A'].front().back() = faces_dates['U' - 'A'].front().back();
  74.                 faces_dates['B' - 'A'].back().back()  = faces_dates['U' - 'A'].back().back();
  75.  
  76.                 faces_dates['U' - 'A'].front().back() = save_upper_right_F;
  77.                 faces_dates['U' - 'A'].back().back()  = save_lower_right_F;
  78.  
  79.                 RotateFaceForward('R');
  80.                 return;
  81.             }
  82.  
  83.             if (face == 'B' || face == 'F') {
  84.                 char save_upper_right_R = faces_dates['R' - 'A'].front().back();
  85.                 char save_lower_right_R = faces_dates['R' - 'A'].back().back();
  86.  
  87.                 faces_dates['F' - 'A'].front().back() = faces_dates['D' - 'A'].front().back();
  88.                 faces_dates['F' - 'A'].back().back() = faces_dates['D' - 'A'].back().back();
  89.  
  90.                 faces_dates['R' - 'A'].front().back() = faces_dates['B' - 'A'].front().back();
  91.                 faces_dates['R' - 'A'].back().back() = faces_dates['B' - 'A'].back().back();
  92.  
  93.                 faces_dates['B' - 'A'].front().back() = faces_dates['U' - 'A'].front().back();
  94.                 faces_dates['B' - 'A'].back().back() = faces_dates['U' - 'A'].back().back();
  95.  
  96.                 faces_dates['U' - 'A'].front().back() = save_upper_right_F;
  97.                 faces_dates['U' - 'A'].back().back() = save_lower_right_F;
  98.  
  99.  
  100.  
  101.                 RotateFaceForward('B');
  102.                 return;
  103.             }
  104.  
  105.             if (face == 'U' || face == 'D') {
  106.  
  107.                 RotateFaceForward('U');
  108.                 return;
  109.             }
  110.         }
  111.        
  112.         if (direction == BACK) {
  113.             //передняя (F), левая (L), задняя (B), правая (R), верхняя (U) и нижняя (D)
  114.             if (face == 'R' || face == 'L') {
  115.  
  116.                 RotateFaceBack('R');
  117.                 return;
  118.             }
  119.  
  120.             if (face == 'B' || face == 'F') {
  121.  
  122.                 RotateFaceBack('B');
  123.                 return;
  124.             }
  125.  
  126.             if (face == 'U' || face == 'D') {
  127.  
  128.                 RotateFaceBack('U');
  129.                 return;
  130.             }
  131.         }
  132.     }
  133.  
  134.     string GetValues() const {
  135.         string values;
  136.         for (const auto& face_date : faces_dates) {
  137.             for (const auto& row : face_date) {
  138.                 for (char c : row) {
  139.                     values += c;
  140.                 }
  141.             }
  142.         }
  143.         return values;
  144.     }
  145.  
  146.     vector<vector<vector<char>>> faces_dates;
  147. };
  148.  
  149. bool operator<(const RubiksCube& lhs, const RubiksCube& rhs) {
  150.     return lhs.GetValues() < rhs.GetValues();
  151. }
  152.  
  153. bool operator==(const RubiksCube& lhs, const RubiksCube& rhs) {
  154.     return lhs.GetValues() == rhs.GetValues();
  155. }
  156.  
  157. int main() {
  158.     RubiksCube rubiks_cube;
  159.     if (rubiks_cube.IsSolved()) {
  160.         cout << "Solved";
  161.         return 0;
  162.     }
  163.  
  164.     map<RubiksCube, string> rubiks_cube_states_to_rotations;
  165.     rubiks_cube_states_to_rotations[rubiks_cube];
  166.     queue<RubiksCube> q;
  167.     q.push(rubiks_cube);
  168.     while (!q.empty()) {
  169.         auto cur_cube = q.front();
  170.         q.pop();
  171.  
  172.         if (cur_cube.IsSolved()) {
  173.             cout << "Solved";
  174.             return 0;
  175.         }
  176.  
  177.         const vector<int> directions = { BACK, FORWARD };
  178.         for (auto cube_face : FACES) {
  179.             for (auto direction : directions) {
  180.                 auto cube = cur_cube;
  181.                 cube.DoRotate(cube_face, direction);
  182.                 if (rubiks_cube_states_to_rotations.count(cube) != 0) continue;
  183.  
  184.                 string rotation = string{ cube_face };
  185.                 if (direction == BACK) rotation = "'" + rotation;
  186.  
  187.                 rubiks_cube_states_to_rotations[cube] = rubiks_cube_states_to_rotations[cur_cube] + rotation;
  188.                 q.push(cube);
  189.             }
  190.         }
  191.     }
  192.  
  193.     return 0;
  194. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement