Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define DONE 1147797409030816545
- #include <sstream>
- #include <iostream>
- #include <queue>
- using namespace std;
- const unsigned long long Masks[] = {
- 0x000000000000000F,
- 0x00000000000000F0,
- 0x0000000000000F00,
- 0x000000000000F000,
- 0x00000000000F0000,
- 0x0000000000F00000,
- 0x000000000F000000,
- 0x00000000F0000000,
- 0x0000000F00000000,
- 0x000000F000000000,
- 0x00000F0000000000,
- 0x0000F00000000000,
- 0x000F000000000000,
- 0x00F0000000000000,
- 0x0F00000000000000,
- 0xF000000000000000,
- };
- const unsigned long long AntiMasks[] = {
- 0xFFFFFFFFFFFFFFF0,
- 0xFFFFFFFFFFFFFF0F,
- 0xFFFFFFFFFFFFF0FF,
- 0xFFFFFFFFFFFF0FFF,
- 0xFFFFFFFFFFF0FFFF,
- 0xFFFFFFFFFF0FFFFF,
- 0xFFFFFFFFF0FFFFFF,
- 0xFFFFFFFF0FFFFFFF,
- 0xFFFFFFF0FFFFFFFF,
- 0xFFFFFF0FFFFFFFFF,
- 0xFFFFF0FFFFFFFFFF,
- 0xFFFF0FFFFFFFFFFF,
- 0xFFF0FFFFFFFFFFFF,
- 0xFF0FFFFFFFFFFFFF,
- 0xF0FFFFFFFFFFFFFF,
- 0x0FFFFFFFFFFFFFFF
- };
- struct Puzzle {
- unsigned long long data; //Само состояние
- string Prev; // Предки;
- unsigned long long Dist; //Расстояние до конечнего расстояния
- int ZeroPos; //Положение нуля
- unsigned long long Father; //
- Puzzle(string P) : Prev(P), Dist(0), Father(0), ZeroPos(0) {}
- void setAt(int place, unsigned char value);
- unsigned char getAt(int place) const;
- //Эврестика
- unsigned long long Heueristic();
- void Distance();
- };
- void Puzzle::setAt(int place, unsigned char value) {
- data = (data & AntiMasks[place]) | (static_cast<long long>( value ) << (place << 2));
- }
- unsigned char Puzzle::getAt(int place) const {
- return static_cast<unsigned char>((data & Masks[place]) >> (place << 2));
- }
- //Эврестика
- unsigned long long Puzzle::Heueristic() {
- unsigned long long h = 0;
- for (int i = 0; i < 16; i++) {
- char value = getAt(i);
- if (value != 0) {
- int targetX = (value - 1) / 4; // expected x-coordinate (row)
- int targetY = (value - 1) % 4; // expected y-coordinate (col)
- int dx = i / 4 - targetX; // x-distance to expected coordinate
- int dy = i % 4 - targetY; // y-distance to expected coordinate
- h += (abs(dx) + abs(dy));
- }
- }
- return h;
- }
- void Puzzle::Distance() {
- Dist = Prev.size() + Heueristic();
- }
- //Движение вправо
- Puzzle MoveRight(Puzzle l) {
- int pos = l.ZeroPos;
- unsigned char k = l.getAt(pos + 1);
- l.setAt(pos, k);
- l.setAt(pos + 1, 0);
- l.ZeroPos++;
- l.Prev = l.Prev + 'L';
- l.Distance();
- return l;
- }
- //Движение влево
- Puzzle MoveLeft(Puzzle l) {
- int pos = l.ZeroPos;
- unsigned char k = l.getAt(pos - 1);
- l.setAt(pos, k);
- l.setAt(pos - 1, 0);
- l.ZeroPos--;
- l.Prev = l.Prev + 'R';
- l.Distance();
- return l;
- }
- //Движение вверх
- Puzzle MoveUp(Puzzle l) {
- int pos = l.ZeroPos;
- unsigned char k = l.getAt(pos - 4);
- l.setAt(pos, k);
- l.setAt(pos - 4, 0);
- l.ZeroPos -= 4;
- l.Prev = l.Prev + 'D';
- l.Distance();
- return l;
- }
- //Движение вниз
- Puzzle MoveDown(Puzzle l) {
- int pos = l.ZeroPos;
- unsigned char k = l.getAt(pos + 4);
- l.setAt(pos, k);
- l.setAt(pos + 4, 0);
- l.ZeroPos += 4;
- l.Prev = l.Prev + 'U';
- l.Distance();
- return l;
- }
- //Получаем список всех состояний, в которые можно перейти из нынешнего
- vector<Puzzle> getNodes(Puzzle tmp) {
- vector<Puzzle> ToReturn;
- int pos = tmp.ZeroPos;
- if (pos >= 4) {
- Puzzle toPush = MoveUp(tmp);
- if (tmp.Father != toPush.data) {
- ToReturn.push_back(toPush);
- }
- }
- if (pos <= 11) {
- Puzzle toPush = MoveDown(tmp);
- if (tmp.Father != toPush.data) {
- ToReturn.push_back(toPush);
- }
- }
- if (pos % 4 != 3) {
- Puzzle toPush = MoveRight(tmp);
- if (tmp.Father != toPush.data) {
- ToReturn.push_back(toPush);
- }
- }
- if (pos % 4 != 0) {
- Puzzle toPush = MoveLeft(tmp);
- if (tmp.Father != toPush.data) {
- ToReturn.push_back(toPush);
- }
- }
- return ToReturn;
- }
- //Функция поиска для IDA
- Puzzle Search(Puzzle node, unsigned long long bound) {
- if (node.Dist > bound) {
- return node;
- }
- if (node.data == DONE) {
- return node;
- }
- Puzzle min("");
- min.Dist = 100000000;
- vector<Puzzle> vert = getNodes(node);
- for (int i = 0; i < vert.size(); i++) {
- Puzzle tmp = Search(vert[i], bound);
- if (tmp.data == DONE) {
- return tmp;
- }
- if (tmp.Dist < min.Dist) {
- min = tmp;
- }
- }
- return min;
- }
- //Решается ли данное состояние
- bool IsSolved(Puzzle start) {
- int mistakes = start.ZeroPos / 4 + 1; //Переменная для подсчета счетности
- for (int i = 0; i < 16; i++) {
- for (int j = i + 1; j < 16; j++) {
- int f1 = i / 4;
- int f2 = i % 4;
- int s1 = j / 4;
- int s2 = j % 4;
- int first = start.getAt(f1 * 4 + f2);
- int second = start.getAt(s1 * 4 + s2);
- if (first != 0 && second != 0) {
- if (first > second) {
- mistakes++;
- }
- }
- }
- }
- if (mistakes % 2 != 0) {
- return false;
- }
- return true;
- }
- string IDA(Puzzle start) {
- start.Distance();
- unsigned long long bound = start.Dist;
- while (1) {
- Puzzle tmp = Search(start, bound);
- if (tmp.data == DONE) {
- return tmp.Prev;
- }
- bound = tmp.Dist;
- }
- }
- int main() {
- Puzzle start(""); //Начальное состояние
- //Считываем состояние
- int ZeroPos = 0;
- for (int i = 0; i < 16; i++) {
- int Input;
- cin >> Input;
- start.setAt(i, Input);
- if (Input == 0) {
- ZeroPos = i;
- }
- }
- start.ZeroPos = ZeroPos;
- //Проверяем на решаемость
- if (!IsSolved(start)) {
- cout << "-1";
- return 0;
- }
- //Если решается, то находим ответ и выводим
- string answer = IDA(start);
- cout << answer.length();
- cout << "\n";
- cout << answer;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement