daily pastebin goal
57%
SHARE
TWEET

Untitled

a guest Mar 23rd, 2019 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2.  
  3. #include <iostream>
  4. #include <vector>
  5. #include <cstdint>
  6. #include <unordered_map>
  7. #include <queue>
  8.  
  9. template <int size>
  10. class Board {
  11. private:
  12.     struct State {
  13.         State() = default;
  14.  
  15.         State(uint64_t state, size_t zero_index, size_t width);
  16.  
  17.         State(const std::vector<size_t>& combinations, size_t width);
  18.  
  19.         bool operator== (const State& rhv);
  20.  
  21.         size_t Get(size_t index) const; // декодирует конфигурацию и возвращает число
  22.                                              // находящееся по индексу
  23.         void Set(size_t index, size_t number); // заменяет число в конфигурации
  24.                                                    // на переданное
  25.         bool CanMoveUp() const;
  26.  
  27.         bool CanMoveDown() const;
  28.  
  29.         bool CanMoveRight() const;
  30.  
  31.         bool CanMoveLeft() const;
  32.  
  33.         State MoveUp() const;
  34.  
  35.         State MoveDown() const;
  36.  
  37.         State MoveLeft() const;
  38.  
  39.         State MoveRight() const;
  40.  
  41.         uint64_t GetState() const;
  42.     private:
  43.         uint64_t state_ = 0;
  44.         size_t zero_index_;
  45.         size_t width_;
  46.         static const std::vector<uint64_t> masks_;
  47.         static const std::vector<uint64_t> anti_masks_;
  48.     };
  49.  
  50.     bool ExistSolution(std::vector<size_t > positions) const;  // Проверяет существование решения (служебная)
  51.  
  52.     State source_;   // изначальная конфигурация доски
  53.     State target_;    // конфигурация финиша
  54.     std::unordered_map<uint64_t , std::pair<uint64_t , int>> parents_;
  55.     size_t board_width_;
  56.     bool have_solution_;
  57. public:
  58.     Board(const std::vector<size_t>& positions);
  59.  
  60.     std::vector<State> GetNext(State vertex) const;  //  Возвращает всевозможные расстановки чисел, получаемые
  61.                                                        // из исходного положения выполнением хода
  62.     bool HaveSolution();   // Проверяет существование решения (публичная)
  63.  
  64.     std::pair<int, std::vector<char>> FindWinningConfiguration();
  65.  
  66. };
  67.  
  68.  
  69. int main() {
  70.     const int size = 9;
  71.     std::vector<size_t> combination;
  72.     for (auto i = 0; i < size; ++i) {
  73.         size_t number;
  74.         std::cin >> number;
  75.         combination.push_back(number);
  76.     }
  77.     Board<size> board(combination);
  78.     if (!board.HaveSolution()) {
  79.         std::cout << -1;
  80.     }
  81.     else {
  82.         std::pair<size_t, std::vector<char>> game_solution;
  83.         game_solution = board.FindWinningConfiguration();
  84.         std::cout << game_solution.first << std::endl;
  85.         for (auto movement : game_solution.second) {
  86.             std::cout << movement;
  87.         }
  88.     }
  89.     return 0;
  90. }
  91.  
  92. template <int size>
  93. std::pair<int, std::vector<char>> Board<size>::FindWinningConfiguration() {
  94.     std::queue<State> vertices;
  95.     vertices.push(source_);
  96.     bool find = false;
  97.     uint64_t target_state;
  98.     while (!find) {                  // идем BFS'ом, пока не наткнемся на победную конфигурацию
  99.         State current_vertex = vertices.front();
  100.         vertices.pop();
  101.         std::vector<State> next_vertices = GetNext(current_vertex);
  102.         for (int i = 0; i < next_vertices.size(); ++i) {
  103.             if (next_vertices[i] == target_) {
  104.                 find = true;
  105.                 target_state = next_vertices[i].GetState();
  106.                 parents_[next_vertices[i].GetState()] = {current_vertex.GetState(), i};
  107.             }
  108.             if (next_vertices[i].GetState() != 0 && parents_.find(next_vertices[i].GetState()) == parents_.end()) {
  109.                 vertices.push(next_vertices[i]);
  110.                 parents_[next_vertices[i].GetState()] = {current_vertex.GetState(), i};
  111.             }
  112.         }
  113.     }
  114.     size_t distance = 0;
  115.     std::vector<int> steps;
  116.     std::vector<char> movements;
  117.     State current_vertex(target_state, 0, board_width_);
  118.     while (parents_[current_vertex.GetState()].first != 0) {   // по предкам поднимаемся до исходной конфигурации,
  119.         distance += 1;                                         // попутно увеличивая дистанцию и запоминая переходы
  120.         steps.push_back(parents_[current_vertex.GetState()].second);
  121.         current_vertex = State(parents_[current_vertex.GetState()].first, 0, board_width_);
  122.     }
  123.     for (int i = static_cast<int>(steps.size()) - 1; i >= 0; --i) {    // обработка переходов
  124.         if (steps[i] == 0) {
  125.             movements.push_back('D');
  126.         }
  127.         else if (steps[i] == 1) {
  128.             movements.push_back('U');
  129.         }
  130.         else if (steps[i] == 2) {
  131.             movements.push_back('L');
  132.         }
  133.         else {
  134.             movements.push_back('R');
  135.         }
  136.     }
  137.     return {distance, movements};
  138. }
  139.  
  140. template <int size>
  141. bool Board<size>::HaveSolution() {
  142.     return have_solution_;
  143. }
  144.  
  145. template <int size>
  146. bool Board<size>::ExistSolution(std::vector<size_t> positions) const {
  147.     std::vector<size_t> sequence_checker;
  148.     std::vector<size_t> subsequence;
  149.     size_t i = 0;
  150.     size_t row = 1;                                      // организация исходного массива расстановки
  151.     size_t zero_ind = 0;                                 // в расстановку змейкой для определения количества инверсий
  152.     size_t inversions = 0;                              
  153.     while (sequence_checker.size() != positions.size()) {
  154.         while (subsequence.size() != board_width_) {
  155.             subsequence.push_back(positions[i]);
  156.             i += 1;
  157.         }
  158.         if (row % 2) {
  159.             for (auto j = 0; j < board_width_; ++j) {
  160.                 sequence_checker.push_back(subsequence[j]);
  161.                 if (sequence_checker[sequence_checker.size() - 1] == 0) {
  162.                     zero_ind = sequence_checker.size() - 1;
  163.                 }
  164.             }
  165.         }
  166.         else {
  167.             for (int j = static_cast<int>(subsequence.size()) - 1; j >= 0; --j) {
  168.                 sequence_checker.push_back(subsequence[j]);
  169.                 if (sequence_checker[sequence_checker.size() - 1] == 0) {
  170.                     zero_ind = sequence_checker.size() - 1;
  171.                 }
  172.             }
  173.         }
  174.         row += 1;
  175.         subsequence.clear();
  176.     }
  177.     for (auto j = zero_ind; j < sequence_checker.size(); ++j) {
  178.         if (zero_ind == sequence_checker.size() - 1) {
  179.             break;
  180.         }
  181.         else {
  182.             sequence_checker[j] = sequence_checker[j + 1];
  183.         }
  184.     }
  185.     for (auto j = 0; j < sequence_checker.size() - 1; ++j) {         // подсчет инверсий
  186.         for (auto p = j; p < sequence_checker.size() - 1; ++p) {
  187.             if (sequence_checker[j] > sequence_checker[p]) {
  188.                 inversions += 1;
  189.             }
  190.         }
  191.     }
  192.     return static_cast<bool>((inversions % 2));
  193. }
  194.  
  195. template <int size>
  196. std::vector<class Board<size>::State> Board<size>::GetNext(Board<size>::State vertex) const {
  197.     std::vector<class Board<size>::State> next_vertices;   // если какое-либо движение невыполнимо, то возвращаем пустышку
  198.     (vertex.CanMoveDown()) ? next_vertices.push_back(vertex.MoveDown()) : next_vertices.push_back(State(0, 0, board_width_));
  199.     (vertex.CanMoveUp()) ? next_vertices.push_back(vertex.MoveUp()) : next_vertices.push_back(State(0, 0, board_width_));
  200.     (vertex.CanMoveLeft()) ? next_vertices.push_back(vertex.MoveLeft()) : next_vertices.push_back(State(0, 0, board_width_));
  201.     (vertex.CanMoveRight()) ? next_vertices.push_back(vertex.MoveRight()) : next_vertices.push_back(State(0, 0, board_width_));
  202.     return next_vertices;
  203. }
  204.  
  205. template <int size>
  206. bool Board<size>::State::operator==(const class Board<size>::State& rhv) {
  207.     return  state_ == rhv.state_;
  208. };
  209.  
  210. template <int size>
  211. bool Board<size>::State::CanMoveLeft() const {
  212.     return zero_index_ % width_ != 0;
  213. }
  214.  
  215. template <int size>
  216. bool Board<size>::State::CanMoveUp() const {
  217.     return zero_index_ > width_ - 1;
  218. }
  219.  
  220. template <int size>
  221. bool Board<size>::State::CanMoveDown() const {
  222.     return zero_index_ < size - width_;
  223. }
  224.  
  225. template <int size>
  226. bool Board<size>::State::CanMoveRight() const {
  227.     return  (zero_index_ + 1) % width_ != 0;
  228. }
  229.  
  230. template <int size>
  231. Board<size>::State::State(uint64_t state, size_t zero_index, size_t width)
  232. : state_(state)
  233. , zero_index_(zero_index)
  234. , width_(width)
  235. {}
  236.  
  237. template <int size>
  238. class Board<size>::State Board<size>::State::MoveLeft() const {
  239.         State moved_left(state_, zero_index_ - 1, width_);
  240.         size_t digit = this->Get(zero_index_ - 1);
  241.         moved_left.Set(zero_index_ - 1, 0);
  242.         moved_left.Set(zero_index_, digit);
  243.         return moved_left;
  244. }
  245.  
  246. template <int size>
  247. class Board<size>::State Board<size>::State::MoveUp() const {
  248.         State moved_up(state_, zero_index_ - width_, width_);
  249.         size_t digit = this->Get(zero_index_ - width_);
  250.         moved_up.Set(zero_index_ - width_, 0);
  251.         moved_up.Set(zero_index_, digit);
  252.         return moved_up;
  253. }
  254.  
  255. template <int size>
  256. class Board<size>::State Board<size>::State::MoveRight() const {
  257.         State moved_right(state_, zero_index_ + 1, width_);
  258.         size_t digit = this->Get(zero_index_ + 1);
  259.         moved_right.Set(zero_index_ + 1, 0);
  260.         moved_right.Set(zero_index_, digit);
  261.         return moved_right;
  262. }
  263.  
  264. template <int size>
  265. class Board<size>::State Board<size>::State::MoveDown() const {
  266.         State moved_down(state_, zero_index_ + width_, width_);
  267.         size_t digit = this->Get(zero_index_ + width_);
  268.         moved_down.Set(zero_index_ + width_, 0);
  269.         moved_down.Set(zero_index_, digit);
  270.         return moved_down;
  271. }
  272.  
  273. template <int size>
  274. Board<size>::Board(const std::vector<size_t>& positions)
  275. {
  276.         size_t n = 1;
  277.         while (n * n != size) {
  278.             n += 1;
  279.         }
  280.         board_width_ = n;
  281.         std::vector<size_t> target;
  282.         for (int i = 1; i < size; ++i) {
  283.             target.push_back(i);
  284.         }
  285.         target.push_back(0);
  286.         target_ = State(target, n);
  287.         source_ = State(positions, n);
  288.         parents_[source_.GetState()] = {0, 0};
  289.         have_solution_ = ExistSolution(positions);
  290. }
  291.  
  292. template <int size>
  293. Board<size>::State::State(const std::vector<size_t>& combinations, size_t width)
  294. : width_(width)
  295. {
  296.     for (size_t i = 0; i < combinations.size(); ++i) {
  297.         if (combinations[i] == 0) {
  298.             zero_index_ = i;
  299.         }
  300.         state_ = state_ << 4;
  301.         state_ += combinations[i];
  302.     }
  303.  
  304. }
  305.  
  306. template <int size>
  307. uint64_t Board<size>::State::GetState() const {
  308.     return state_;
  309. }
  310.  
  311. template <int size>
  312. size_t Board<size>::State::Get(size_t index) const {
  313.     size_t digit = state_ & masks_[masks_.size() - size + index];
  314.     digit = digit >> 4 * (size - index - 1);
  315.     return digit;
  316. }
  317.  
  318. template <int size>
  319. void Board<size>::State::Set(size_t index, size_t number) {
  320.     uint64_t digit = static_cast<uint64_t >(number);
  321.     digit = digit << 4 * (size - index - 1);
  322.     state_ = state_ & anti_masks_[masks_.size() - size + index];
  323.     state_ = state_ | digit;
  324. }
  325.  
  326. template<int size>
  327. const std::vector<uint64_t> Board<size>::State::masks_ = {17293822569102704640u, 1080863910568919040u,
  328.                                                           67553994410557440u, 4222124650659840u, 263882790666240u,
  329.                                                           16492674416640u, 1030792151040u, 64424509440u, 4026531840u,
  330.                                                           251658240u, 15728640u, 983040u, 61440u, 3840u, 240u, 15u};
  331. template<int size>
  332. const std::vector<uint64_t> Board<size>::State::anti_masks_ = {1152921504606846975u, 17365880163140632575u,
  333.                                                                18379190079298994175u, 18442521949058891775u,
  334.                                                                18446480190918885375u, 18446727581035134975u,
  335.                                                                18446743042917400575u, 18446744009285042175u,
  336.                                                                18446744069683019775u, 18446744073457893375u,
  337.                                                                18446744073693822975u, 18446744073708568575u,
  338.                                                                18446744073709490175u, 18446744073709547775u,
  339.                                                                18446744073709551375u, 18446744073709551600u};
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top