Advertisement
Guest User

Untitled

a guest
Mar 21st, 2018
109
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.19 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <unordered_set>
  5.  
  6. struct Vosminashka{
  7.     std::vector<std::vector<int> > table;
  8.     std::string way;
  9.     Vosminashka();
  10.     int operator[](int i) const;
  11.     long long getHash() const;
  12.     void down();
  13.     void up();
  14.     void left();
  15.     void right();
  16.     void addStep(char c);
  17.     bool endOfGame() const;
  18. };
  19.  
  20. Vosminashka::Vosminashka() {
  21.     table = std::vector<std::vector<int> >(3,std::vector<int>(3));
  22. }
  23.  
  24. int Vosminashka::operator[](int i) const{
  25.     if(i < 9){
  26.         return table[i/3][i%3];
  27.     } else {
  28.         return -1;
  29.     }
  30. }
  31.  
  32. long long Vosminashka::getHash() const{
  33.     long long result = 0;
  34.     long long deg = 10;
  35.     for(int i = 0; i < 9; ++i){
  36.         result += this->operator[](i)*deg;
  37.         deg*=10;
  38.     }
  39.     return result;
  40. }
  41.  
  42. void Vosminashka::up() {
  43.     for(int i = 1; i < 3; ++i){
  44.         for(int j = 0; j < 3; ++j){
  45.             if(table[i][j] == 0){
  46.                 std::swap(table[i][j],table[i-1][j]);
  47.                 return;
  48.             }
  49.         }
  50.     }
  51. }
  52.  
  53. void Vosminashka::down() {
  54.     for(int i = 0; i < 2; ++i){
  55.         for(int j = 0; j < 3; ++j){
  56.             if(table[i][j] == 0){
  57.                 std::swap(table[i][j],table[i+1][j]);
  58.                 return;
  59.             }
  60.         }
  61.     }
  62. }
  63.  
  64. void Vosminashka::left() {
  65.     for(int i = 0; i < 3; ++i){
  66.         for(int j = 1; j < 3; ++j){
  67.             if(table[i][j] == 0){
  68.                 std::swap(table[i][j-1],table[i][j]);
  69.                 return;
  70.             }
  71.         }
  72.     }
  73. }
  74.  
  75. void Vosminashka::right() {
  76.     for(int i = 0; i < 3; ++i){
  77.         for(int j = 0; j < 2; ++j){
  78.             if(table[i][j] == 0){
  79.                 std::swap(table[i][j],table[i][j+1]);
  80.                 return;
  81.             }
  82.         }
  83.     }
  84. }
  85.  
  86. void Vosminashka::addStep(char c) {
  87.     way+=c;
  88. }
  89.  
  90. bool Vosminashka::endOfGame() const{
  91.     if(table[2][2] != 0)
  92.         return false;
  93.     for(int i = 1; i < 8; ++i){
  94.         if(this->operator[](i) < this->operator[](i-1)) {
  95.             return false;
  96.         }
  97.     }
  98.     return true;
  99. }
  100.  
  101. bool possibleSolution(Vosminashka const &game){
  102.     int counter = 0;
  103.     for(int i = 0; i < 8; ++i){
  104.         for(int j = i + 1; j < 9; ++j){
  105.             if(game[i] > game[j] && game[i] != 0 && game[j] != 0)
  106.                 ++counter;
  107.         }
  108.     }
  109.  
  110.     return counter%2 == 0;
  111.  
  112. }
  113.  
  114. Vosminashka win(Vosminashka game){
  115.     if(!possibleSolution(game)) {
  116.         game.addStep('0');
  117.         return game;
  118.     }
  119.  
  120.     std::deque<Vosminashka> bfsDeque;
  121.     std::unordered_set<long long> used;
  122.     used.insert(game.getHash());
  123.     bfsDeque.push_back(game);
  124.     while(!bfsDeque.empty()){
  125.         Vosminashka curGame = bfsDeque.front();
  126.         if(curGame.endOfGame()) {
  127.             return curGame;
  128.         }
  129.         bfsDeque.pop_front();
  130.  
  131.         Vosminashka newGame = curGame;
  132.         newGame.down();
  133.         if(used.find(newGame.getHash()) == used.end()){
  134.             newGame.addStep('D');
  135.             bfsDeque.push_back(newGame);
  136.             used.insert(newGame.getHash());
  137.         }
  138.  
  139.         newGame = curGame;
  140.         newGame.up();
  141.         if(used.find(newGame.getHash()) == used.end()){
  142.             newGame.addStep('U');
  143.             bfsDeque.push_back(newGame);
  144.             used.insert(newGame.getHash());
  145.         }
  146.  
  147.         newGame = curGame;
  148.         newGame.left();
  149.         if(used.find(newGame.getHash()) == used.end()){
  150.             newGame.addStep('L');
  151.             bfsDeque.push_back(newGame);
  152.             used.insert(newGame.getHash());
  153.         }
  154.  
  155.         newGame = curGame;
  156.         newGame.right();
  157.         if(used.find(newGame.getHash()) == used.end()){
  158.             newGame.addStep('R');
  159.             bfsDeque.push_back(newGame);
  160.             used.insert(newGame.getHash());
  161.  
  162.         }
  163.  
  164.     }
  165.  
  166.     return game;
  167.  
  168. }
  169.  
  170.  
  171. int main() {
  172.     Vosminashka game;
  173.     for(int i = 0; i < 9; ++i){
  174.         std::cin >> game.table[i/3][i%3];
  175.     }
  176.     Vosminashka result = win(game);
  177.     if(result.way == "0") {
  178.         std::cout << "-1";
  179.     } else{
  180.         std::cout << result.way.size() << std::endl;
  181.         std::cout << result.way;
  182.     }
  183.  
  184.     return 0;
  185.  
  186. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement