Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- #include <unordered_set>
- struct Vosminashka{
- std::vector<std::vector<int> > table;
- std::string way;
- Vosminashka();
- int operator[](int i) const;
- long long getHash() const;
- void down();
- void up();
- void left();
- void right();
- void addStep(char c);
- bool endOfGame() const;
- };
- Vosminashka::Vosminashka() {
- table = std::vector<std::vector<int> >(3,std::vector<int>(3));
- }
- int Vosminashka::operator[](int i) const{
- if(i < 9){
- return table[i/3][i%3];
- } else {
- return -1;
- }
- }
- long long Vosminashka::getHash() const{
- long long result = 0;
- long long deg = 10;
- for(int i = 0; i < 9; ++i){
- result += this->operator[](i)*deg;
- deg*=10;
- }
- return result;
- }
- void Vosminashka::up() {
- for(int i = 1; i < 3; ++i){
- for(int j = 0; j < 3; ++j){
- if(table[i][j] == 0){
- std::swap(table[i][j],table[i-1][j]);
- return;
- }
- }
- }
- }
- void Vosminashka::down() {
- for(int i = 0; i < 2; ++i){
- for(int j = 0; j < 3; ++j){
- if(table[i][j] == 0){
- std::swap(table[i][j],table[i+1][j]);
- return;
- }
- }
- }
- }
- void Vosminashka::left() {
- for(int i = 0; i < 3; ++i){
- for(int j = 1; j < 3; ++j){
- if(table[i][j] == 0){
- std::swap(table[i][j-1],table[i][j]);
- return;
- }
- }
- }
- }
- void Vosminashka::right() {
- for(int i = 0; i < 3; ++i){
- for(int j = 0; j < 2; ++j){
- if(table[i][j] == 0){
- std::swap(table[i][j],table[i][j+1]);
- return;
- }
- }
- }
- }
- void Vosminashka::addStep(char c) {
- way+=c;
- }
- bool Vosminashka::endOfGame() const{
- if(table[2][2] != 0)
- return false;
- for(int i = 1; i < 8; ++i){
- if(this->operator[](i) < this->operator[](i-1)) {
- return false;
- }
- }
- return true;
- }
- bool possibleSolution(Vosminashka const &game){
- int counter = 0;
- for(int i = 0; i < 8; ++i){
- for(int j = i + 1; j < 9; ++j){
- if(game[i] > game[j] && game[i] != 0 && game[j] != 0)
- ++counter;
- }
- }
- return counter%2 == 0;
- }
- Vosminashka win(Vosminashka game){
- if(!possibleSolution(game)) {
- game.addStep('0');
- return game;
- }
- std::deque<Vosminashka> bfsDeque;
- std::unordered_set<long long> used;
- used.insert(game.getHash());
- bfsDeque.push_back(game);
- while(!bfsDeque.empty()){
- Vosminashka curGame = bfsDeque.front();
- if(curGame.endOfGame()) {
- return curGame;
- }
- bfsDeque.pop_front();
- Vosminashka newGame = curGame;
- newGame.down();
- if(used.find(newGame.getHash()) == used.end()){
- newGame.addStep('D');
- bfsDeque.push_back(newGame);
- used.insert(newGame.getHash());
- }
- newGame = curGame;
- newGame.up();
- if(used.find(newGame.getHash()) == used.end()){
- newGame.addStep('U');
- bfsDeque.push_back(newGame);
- used.insert(newGame.getHash());
- }
- newGame = curGame;
- newGame.left();
- if(used.find(newGame.getHash()) == used.end()){
- newGame.addStep('L');
- bfsDeque.push_back(newGame);
- used.insert(newGame.getHash());
- }
- newGame = curGame;
- newGame.right();
- if(used.find(newGame.getHash()) == used.end()){
- newGame.addStep('R');
- bfsDeque.push_back(newGame);
- used.insert(newGame.getHash());
- }
- }
- return game;
- }
- int main() {
- Vosminashka game;
- for(int i = 0; i < 9; ++i){
- std::cin >> game.table[i/3][i%3];
- }
- Vosminashka result = win(game);
- if(result.way == "0") {
- std::cout << "-1";
- } else{
- std::cout << result.way.size() << std::endl;
- std::cout << result.way;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement