Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cstdint>
- #include <unordered_map>
- #include <queue>
- template <int size>
- class Board {
- private:
- struct State {
- State() = default;
- State(uint64_t state, size_t zero_index, size_t width);
- State(const std::vector<size_t>& combinations, size_t width);
- bool operator== (const State& rhv);
- size_t Get(size_t index) const; // декодирует конфигурацию и возвращает число
- // находящееся по индексу
- void Set(size_t index, size_t number); // заменяет число в конфигурации
- // на переданное
- bool CanMoveUp() const;
- bool CanMoveDown() const;
- bool CanMoveRight() const;
- bool CanMoveLeft() const;
- State MoveUp() const;
- State MoveDown() const;
- State MoveLeft() const;
- State MoveRight() const;
- uint64_t GetState() const;
- private:
- uint64_t state_ = 0;
- size_t zero_index_;
- size_t width_;
- static const std::vector<uint64_t> masks_;
- static const std::vector<uint64_t> anti_masks_;
- };
- bool ExistSolution(std::vector<size_t > positions) const; // Проверяет существование решения (служебная)
- State source_; // изначальная конфигурация доски
- State target_; // конфигурация финиша
- std::unordered_map<uint64_t , std::pair<uint64_t , int>> parents_;
- size_t board_width_;
- bool have_solution_;
- public:
- Board(const std::vector<size_t>& positions);
- std::vector<State> GetNext(State vertex) const; // Возвращает всевозможные расстановки чисел, получаемые
- // из исходного положения выполнением хода
- bool HaveSolution(); // Проверяет существование решения (публичная)
- std::pair<int, std::vector<char>> FindWinningConfiguration();
- };
- int main() {
- const int size = 9;
- std::vector<size_t> combination;
- for (auto i = 0; i < size; ++i) {
- size_t number;
- std::cin >> number;
- combination.push_back(number);
- }
- Board<size> board(combination);
- if (!board.HaveSolution()) {
- std::cout << -1;
- }
- else {
- std::pair<size_t, std::vector<char>> game_solution;
- game_solution = board.FindWinningConfiguration();
- std::cout << game_solution.first << std::endl;
- for (auto movement : game_solution.second) {
- std::cout << movement;
- }
- }
- return 0;
- }
- template <int size>
- std::pair<int, std::vector<char>> Board<size>::FindWinningConfiguration() {
- std::queue<State> vertices;
- vertices.push(source_);
- bool find = false;
- uint64_t target_state;
- while (!find) { // идем BFS'ом, пока не наткнемся на победную конфигурацию
- State current_vertex = vertices.front();
- vertices.pop();
- std::vector<State> next_vertices = GetNext(current_vertex);
- for (int i = 0; i < next_vertices.size(); ++i) {
- if (next_vertices[i] == target_) {
- find = true;
- target_state = next_vertices[i].GetState();
- parents_[next_vertices[i].GetState()] = {current_vertex.GetState(), i};
- }
- if (next_vertices[i].GetState() != 0 && parents_.find(next_vertices[i].GetState()) == parents_.end()) {
- vertices.push(next_vertices[i]);
- parents_[next_vertices[i].GetState()] = {current_vertex.GetState(), i};
- }
- }
- }
- size_t distance = 0;
- std::vector<int> steps;
- std::vector<char> movements;
- State current_vertex(target_state, 0, board_width_);
- while (parents_[current_vertex.GetState()].first != 0) { // по предкам поднимаемся до исходной конфигурации,
- distance += 1; // попутно увеличивая дистанцию и запоминая переходы
- steps.push_back(parents_[current_vertex.GetState()].second);
- current_vertex = State(parents_[current_vertex.GetState()].first, 0, board_width_);
- }
- for (int i = static_cast<int>(steps.size()) - 1; i >= 0; --i) { // обработка переходов
- if (steps[i] == 0) {
- movements.push_back('D');
- }
- else if (steps[i] == 1) {
- movements.push_back('U');
- }
- else if (steps[i] == 2) {
- movements.push_back('L');
- }
- else {
- movements.push_back('R');
- }
- }
- return {distance, movements};
- }
- template <int size>
- bool Board<size>::HaveSolution() {
- return have_solution_;
- }
- template <int size>
- bool Board<size>::ExistSolution(std::vector<size_t> positions) const {
- std::vector<size_t> sequence_checker;
- std::vector<size_t> subsequence;
- size_t i = 0;
- size_t row = 1; // организация исходного массива расстановки
- size_t zero_ind = 0; // в расстановку змейкой для определения количества инверсий
- size_t inversions = 0;
- while (sequence_checker.size() != positions.size()) {
- while (subsequence.size() != board_width_) {
- subsequence.push_back(positions[i]);
- i += 1;
- }
- if (row % 2) {
- for (auto j = 0; j < board_width_; ++j) {
- sequence_checker.push_back(subsequence[j]);
- if (sequence_checker[sequence_checker.size() - 1] == 0) {
- zero_ind = sequence_checker.size() - 1;
- }
- }
- }
- else {
- for (int j = static_cast<int>(subsequence.size()) - 1; j >= 0; --j) {
- sequence_checker.push_back(subsequence[j]);
- if (sequence_checker[sequence_checker.size() - 1] == 0) {
- zero_ind = sequence_checker.size() - 1;
- }
- }
- }
- row += 1;
- subsequence.clear();
- }
- for (auto j = zero_ind; j < sequence_checker.size(); ++j) {
- if (zero_ind == sequence_checker.size() - 1) {
- break;
- }
- else {
- sequence_checker[j] = sequence_checker[j + 1];
- }
- }
- for (auto j = 0; j < sequence_checker.size() - 1; ++j) { // подсчет инверсий
- for (auto p = j; p < sequence_checker.size() - 1; ++p) {
- if (sequence_checker[j] > sequence_checker[p]) {
- inversions += 1;
- }
- }
- }
- return static_cast<bool>((inversions % 2));
- }
- template <int size>
- std::vector<class Board<size>::State> Board<size>::GetNext(Board<size>::State vertex) const {
- std::vector<class Board<size>::State> next_vertices; // если какое-либо движение невыполнимо, то возвращаем пустышку
- (vertex.CanMoveDown()) ? next_vertices.push_back(vertex.MoveDown()) : next_vertices.push_back(State(0, 0, board_width_));
- (vertex.CanMoveUp()) ? next_vertices.push_back(vertex.MoveUp()) : next_vertices.push_back(State(0, 0, board_width_));
- (vertex.CanMoveLeft()) ? next_vertices.push_back(vertex.MoveLeft()) : next_vertices.push_back(State(0, 0, board_width_));
- (vertex.CanMoveRight()) ? next_vertices.push_back(vertex.MoveRight()) : next_vertices.push_back(State(0, 0, board_width_));
- return next_vertices;
- }
- template <int size>
- bool Board<size>::State::operator==(const class Board<size>::State& rhv) {
- return state_ == rhv.state_;
- };
- template <int size>
- bool Board<size>::State::CanMoveLeft() const {
- return zero_index_ % width_ != 0;
- }
- template <int size>
- bool Board<size>::State::CanMoveUp() const {
- return zero_index_ > width_ - 1;
- }
- template <int size>
- bool Board<size>::State::CanMoveDown() const {
- return zero_index_ < size - width_;
- }
- template <int size>
- bool Board<size>::State::CanMoveRight() const {
- return (zero_index_ + 1) % width_ != 0;
- }
- template <int size>
- Board<size>::State::State(uint64_t state, size_t zero_index, size_t width)
- : state_(state)
- , zero_index_(zero_index)
- , width_(width)
- {}
- template <int size>
- class Board<size>::State Board<size>::State::MoveLeft() const {
- State moved_left(state_, zero_index_ - 1, width_);
- size_t digit = this->Get(zero_index_ - 1);
- moved_left.Set(zero_index_ - 1, 0);
- moved_left.Set(zero_index_, digit);
- return moved_left;
- }
- template <int size>
- class Board<size>::State Board<size>::State::MoveUp() const {
- State moved_up(state_, zero_index_ - width_, width_);
- size_t digit = this->Get(zero_index_ - width_);
- moved_up.Set(zero_index_ - width_, 0);
- moved_up.Set(zero_index_, digit);
- return moved_up;
- }
- template <int size>
- class Board<size>::State Board<size>::State::MoveRight() const {
- State moved_right(state_, zero_index_ + 1, width_);
- size_t digit = this->Get(zero_index_ + 1);
- moved_right.Set(zero_index_ + 1, 0);
- moved_right.Set(zero_index_, digit);
- return moved_right;
- }
- template <int size>
- class Board<size>::State Board<size>::State::MoveDown() const {
- State moved_down(state_, zero_index_ + width_, width_);
- size_t digit = this->Get(zero_index_ + width_);
- moved_down.Set(zero_index_ + width_, 0);
- moved_down.Set(zero_index_, digit);
- return moved_down;
- }
- template <int size>
- Board<size>::Board(const std::vector<size_t>& positions)
- {
- size_t n = 1;
- while (n * n != size) {
- n += 1;
- }
- board_width_ = n;
- std::vector<size_t> target;
- for (int i = 1; i < size; ++i) {
- target.push_back(i);
- }
- target.push_back(0);
- target_ = State(target, n);
- source_ = State(positions, n);
- parents_[source_.GetState()] = {0, 0};
- have_solution_ = ExistSolution(positions);
- }
- template <int size>
- Board<size>::State::State(const std::vector<size_t>& combinations, size_t width)
- : width_(width)
- {
- for (size_t i = 0; i < combinations.size(); ++i) {
- if (combinations[i] == 0) {
- zero_index_ = i;
- }
- state_ = state_ << 4;
- state_ += combinations[i];
- }
- }
- template <int size>
- uint64_t Board<size>::State::GetState() const {
- return state_;
- }
- template <int size>
- size_t Board<size>::State::Get(size_t index) const {
- size_t digit = state_ & masks_[masks_.size() - size + index];
- digit = digit >> 4 * (size - index - 1);
- return digit;
- }
- template <int size>
- void Board<size>::State::Set(size_t index, size_t number) {
- uint64_t digit = static_cast<uint64_t >(number);
- digit = digit << 4 * (size - index - 1);
- state_ = state_ & anti_masks_[masks_.size() - size + index];
- state_ = state_ | digit;
- }
- template<int size>
- const std::vector<uint64_t> Board<size>::State::masks_ = {17293822569102704640u, 1080863910568919040u,
- 67553994410557440u, 4222124650659840u, 263882790666240u,
- 16492674416640u, 1030792151040u, 64424509440u, 4026531840u,
- 251658240u, 15728640u, 983040u, 61440u, 3840u, 240u, 15u};
- template<int size>
- const std::vector<uint64_t> Board<size>::State::anti_masks_ = {1152921504606846975u, 17365880163140632575u,
- 18379190079298994175u, 18442521949058891775u,
- 18446480190918885375u, 18446727581035134975u,
- 18446743042917400575u, 18446744009285042175u,
- 18446744069683019775u, 18446744073457893375u,
- 18446744073693822975u, 18446744073708568575u,
- 18446744073709490175u, 18446744073709547775u,
- 18446744073709551375u, 18446744073709551600u};
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement