Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <map>
- #include <string>
- using namespace std;
- short abs(short A) //модуль числа(не знаю зачем написал)
- {
- return A > 0 ? A : -A;
- }
- class matrix //класс хранящий информацию о текущем состоянии восемнашек + перегруженные операторы
- {
- private:
- int ST;
- short matr[12]; // в 0..8 хранится сама матрица, в 9 хранится значение манхэттеновского расстояния для доски, в 10 и 11 хранятся номера клеток которые мы поменяли последний раз
- public:
- matrix(){}
- matrix(short temp[9])
- {
- for (short i = 0; i < 9; ++i)
- matr[i] = temp[i];
- }
- void shift(short i, short n) //поменять местами что-то и 0
- {
- matr[10] = i;
- matr[11] = n;
- n *= 2;
- ++n;
- matr[9] -= abs(i / 3 - ((matr[i] + 8) % 9) / 3)
- + abs(i % 3 - ((matr[i] + 8) % 9) % 3)
- + abs((i + n) / 3 - ((matr[i + n] + 8) % 9) / 3)
- + abs((i + n) % 3 - ((matr[i + n] + 8) % 9) % 3);
- short k = matr[i];
- matr[i] = matr[i + n];
- matr[i + n] = k;
- matr[9] += abs(i / 3 - ((matr[i] + 8) % 9) / 3)
- + abs(i % 3 - ((matr[i] + 8) % 9) % 3)
- + abs((i + n) / 3 - ((matr[i + n] + 8) % 9) / 3)
- + abs((i + n) % 3 - ((matr[i + n] + 8) % 9) % 3);
- ST += 1;
- }
- matrix getParent() //возвращает предыдущее состояние восемнашек
- {
- if ((this->matr[10] == -1) || (this->matr[11] == -1))
- {
- return *this;
- }
- matrix temp(*this);
- temp.shift(this->matr[10], this->matr[11]);
- return temp;
- }
- friend std::istream& operator >> (std::istream& in, matrix& m)
- {
- m.matr[9] = 0;
- for (short i = 0; i < 9; ++i)
- {
- in >> m.matr[i];
- m.matr[9] += abs(i / 3 - ((m.matr[i] + 8) % 9) / 3);
- m.matr[9] += abs(i % 3 - ((m.matr[i] + 8) % 9) % 3);
- }
- m.matr[10] = -1;
- m.matr[11] = -1;
- m.ST = 0;
- return in;
- }
- friend std::ostream& operator << (std::ostream& out, const matrix& m)
- {
- for (short i = 0; i < 9; ++i)
- {
- out << m.matr[i] << (i % 3 == 2 ? "\n" : " ");
- }
- out << "\n";
- return out;
- }
- friend bool operator== (const matrix& left, const matrix& right)
- {
- for (short i = 0; i < 9; ++i)
- {
- if (left.matr[i] != right.matr[i])
- {
- return false;
- }
- }
- return true;
- }
- friend bool operator!= (const matrix& left, const matrix& right){return !(left == right);}
- short h(){return matr[9];}
- int steps(){return ST;}
- short find_zero()
- {
- for (short i = 0; i < 9; ++i)
- if (matr[i] == 0)
- return i;
- return 0;
- }
- };
- matrix make_matrix(short temp[9]){return matrix(temp);}
- class Vosm
- {
- private:
- matrix start;
- matrix finish;
- std::multimap < int, pair<matrix, string > > table; // h(x) + steps; matrix
- public:
- Vosm()
- {
- std::cin >> start;
- }
- void findSolve()
- {
- short temp[9] = {1, 2, 3, 4, 5, 6, 8, 7, 0};
- finish = make_matrix(temp);
- short q = start.h();
- if (q == 0) //если расстояние 0 то ничего делать не надо
- {
- std::cout << "Yes\n0\n";
- return;
- }
- string tmpstr;
- table.insert(make_pair(0, make_pair(start, tmpstr)));
- AStar();
- }
- private:
- /**
- * 0 - right, 1 - down
- */
- bool addV(matrix M, short i, short n, string path, char c)
- {
- matrix temp(M);
- temp.shift(i, n); //меняем местами восемнашки i и n
- if (temp.h() == 2)
- {
- if (temp == finish)
- return false;
- }
- path.push_back(c);
- if (temp != M.getParent()) //проверяем не возвращаемся ли мы в предыдущее состояние
- {
- table.insert(make_pair(temp.h() + temp.steps(), make_pair(temp, path)));
- }
- return true;
- }
- void AStar() //в ходе алгоритма пробуем поменять восемнашку 0 с 4мя соседями(если это возможно)
- //и после этого добавляем состояние в multimap, где ключ это манхэттоновское расстояние
- {
- while(true)
- {
- matrix M = table.begin()->second.first;
- string path = table.begin()->second.second;
- table.erase(table.begin());
- short Z = M.find_zero();
- if (Z % 3 < 2) //right
- {
- if (addV(M, Z, 0, path, 'r') == false)
- {
- std::cout << "No\n";
- return;
- }
- }
- if (Z % 3 > 0) //left
- {
- if (addV(M, Z - 1, 0, path, 'l') == false)
- {
- std::cout << "No\n";
- return;
- }
- }
- if (Z / 3 < 2) //down
- {
- if (addV(M, Z, 1, path, 'd') == false)
- {
- std::cout << "No\n";
- return;
- }
- }
- if (Z / 3 > 0) //up
- {
- if (addV(M, Z - 3, 1, path, 'u') == false)
- {
- std::cout << "No\n";
- return;
- }
- }
- int q = table.begin()->second.first.h();
- if (q == 0)
- {
- std::cout << "Yes\n" << M.steps() + 1 << "\n" << table.begin()->second.second << "\n";
- return;
- }
- }
- }
- };
- int main()
- {
- Vosm sheet;
- sheet.findSolve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement