SHARE
TWEET

Untitled

a guest Dec 14th, 2019 80 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <assert.h>
  4. #include <string>
  5. #include <time.h>
  6.  
  7.  
  8. enum Sides {
  9.     U,
  10.     D,
  11.     L,
  12.     R
  13. };
  14.  
  15. class P {
  16. private:
  17.  
  18.     std::vector <short int> mat;
  19. public:
  20.  
  21.     int parent;
  22.  
  23.     int step;
  24.  
  25.     Sides Side;
  26.  
  27.     P() {}
  28.  
  29.     P(std::vector<short int> m, int s, Sides tmp, int p) : mat{ m }, step{ s }, Side{ tmp }, parent{ p } {}
  30.  
  31.     ~P() {}
  32.  
  33.     int f();
  34.  
  35.     int g();
  36.  
  37.     int h();
  38.  
  39.     bool equal(P second);
  40.  
  41.     bool operator>(P second);
  42.  
  43.     bool operator<(P second);
  44.  
  45.     bool operator==(P second);
  46.  
  47.     int ExistenceOfSolutions();
  48.  
  49.     std::vector<P> ReturnNext(int number);
  50.  
  51.     void Print_P();
  52.  
  53.     unsigned long long int hesh();
  54. };
  55.  
  56.  
  57. unsigned long long int P::hesh() {
  58.     unsigned long long int res = 0;
  59.     for (unsigned long long int i = 0, pow = 1; i < 16; i++, pow *= 16) {
  60.         res += mat.at(i) * pow;
  61.     }
  62.     return res;
  63. }
  64.  
  65.  
  66. void P::Print_P() {
  67.     std::cout << "g: " << this->g() << " h: " << this->h() << std::endl;
  68.     for (int i = 0; i < 16; ++i) {
  69.         std::cout << this->mat.at(i) << ' ';
  70.     }
  71.     std::cout << std::endl;
  72. }
  73.  
  74.  
  75. int P::f() {
  76.     return this->g() + this->h();
  77. }
  78.  
  79.  
  80.  
  81. int P::h() {
  82.         int N{ 4 }, res{ 0 };
  83.         for (int i = 0; i < N * N; ++i)
  84.             if (mat.at(i) != 0)
  85.                 res += abs((mat.at(i) - 1) / N - i / N) + abs((mat.at(i) - 1) - ((mat.at(i) - 1) / N) * N - (i - (i / N) * N));
  86.         for (int i = 0; i < N; ++i){
  87.             int max = -1;
  88.             for (int j = 0; j < N; ++j){
  89.                 if (mat.at(i * N + j) != 0 && (mat.at(i * N + j) - 1) / N == i){
  90.                     if (mat.at(i * N + j) > max) max = mat.at(i * N + j);
  91.                     else res += 2;
  92.                 }
  93.             }
  94.         }
  95.         for (int j = 0; j < N; ++j){
  96.             int max = -1;
  97.             for (int i = 0; i < N; ++i)
  98.                 if (mat.at(i * N + j) != 0 && mat.at(i * N + j) % N == j + 1) {
  99.                     if (mat.at(i * N + j) > max) max = mat.at(i * N + j);
  100.                     else res += 2;
  101.                 }
  102.         }
  103.         return -3 * res;
  104. }
  105.  
  106.  
  107. int P::g() {
  108.     return -(this->step);
  109. }
  110.  
  111.  
  112. bool P::equal(P second) {
  113.     for (int i = 0; i < 16; ++i)
  114.         if (!(this->mat.at(i) == second.mat.at(i))) return false;
  115.     return true;
  116. }
  117.  
  118.  
  119. bool P::operator==(P second) {
  120.     return this->f() == second.f();
  121. }
  122.  
  123.  
  124. bool P::operator>(P second) {
  125.     return this->f() > second.f();
  126. }
  127.  
  128.  
  129. bool P::operator<(P second) {
  130.     return this->f() < second.f();
  131. }
  132.  
  133.  
  134. class Priority_Queue {
  135. private:
  136.  
  137.     std::vector<P> heap;
  138.  
  139. public:
  140.  
  141.     Priority_Queue() {}
  142.  
  143.     ~Priority_Queue() {}
  144.  
  145.     void AddDigit(P digit);
  146.  
  147.     void SiftDown(int num);
  148.  
  149.     P ExtractMax();
  150.  
  151.     bool empty() { return heap.size(); }
  152.  
  153.     void Print_Queue();
  154. };
  155.  
  156.  
  157. void Priority_Queue::Print_Queue() {
  158.     for (int i = 0; i < 10; ++i) std::cout << '-';
  159.     std::cout << std::endl;
  160.     for (int i = 0; i < heap.size(); ++i) {
  161.         heap.at(i).Print_P();
  162.     }
  163.     for (int i = 0; i < 10; ++i) std::cout << '-';
  164.     std::cout << std::endl;
  165. }
  166.  
  167.  
  168. void Priority_Queue::AddDigit(P digit) {
  169.     heap.push_back(digit);
  170.     int index = heap.size() - 1;
  171.     int parent = (index - 1) / 2;
  172.  
  173.     while (index > 0 && heap.at(parent) < heap.at(index)) {
  174.         std::swap(heap.at(index), heap.at(parent));
  175.         index = parent;
  176.         parent = (index - 1) / 2;
  177.     }
  178.  
  179. }
  180.  
  181.  
  182. void Priority_Queue::SiftDown(int num) {
  183.     int leftChild;
  184.     int rightChild;
  185.     int largestChild;
  186.  
  187.     for (; ; )
  188.     {
  189.         leftChild = 2 * num + 1;
  190.         rightChild = 2 * num + 2;
  191.         largestChild = num;
  192.  
  193.         if (leftChild < heap.size() && heap.at(leftChild) > heap.at(largestChild))
  194.         {
  195.             largestChild = leftChild;
  196.         }
  197.  
  198.         if (rightChild < heap.size() && heap.at(rightChild) > heap.at(largestChild))
  199.         {
  200.             largestChild = rightChild;
  201.         }
  202.  
  203.         if (largestChild == num)
  204.         {
  205.             break;
  206.         }
  207.  
  208.         std::swap(heap.at(num), heap.at(largestChild));
  209.         num = largestChild;
  210.     }
  211. }
  212.  
  213.  
  214. P Priority_Queue::ExtractMax() {
  215.     assert(!heap.empty());
  216.  
  217.     P result = heap.at(0);
  218.  
  219.     heap.at(0) = heap.at(heap.size() - 1);
  220.  
  221.     heap.resize(heap.size() - 1);
  222.  
  223.     if (!heap.empty())
  224.         this->SiftDown(0);
  225.     return result;
  226. }
  227.  
  228.  
  229. std::vector<P> P::ReturnNext(int number) {
  230.     int r_i{ 0 };
  231.     for (int i = 0; i < 16; ++i)
  232.         if (mat.at(i) == 0) r_i = i;
  233.  
  234.     std::vector<P> res;
  235.  
  236.     if (r_i < 12) {
  237.         std::vector<short int> tmp_mat = this->mat;
  238.         std::swap(tmp_mat.at(r_i), tmp_mat.at(r_i + 4));
  239.         P tmp{ tmp_mat, this->step + 1, D, number };
  240.         res.push_back(tmp);
  241.     }
  242.  
  243.     if (r_i > 3) {
  244.         std::vector<short int> tmp_mat = this->mat;
  245.         std::swap(tmp_mat.at(r_i), tmp_mat.at(r_i - 4));
  246.         P tmp{ tmp_mat, this->step + 1, U, number };
  247.         res.push_back(tmp);
  248.     }
  249.  
  250.     if (r_i % 4 != 0) {
  251.         std::vector<short int> tmp_mat = this->mat;
  252.         std::swap(tmp_mat.at(r_i), tmp_mat.at(r_i - 1));
  253.         P tmp{ tmp_mat, this->step + 1, L, number };
  254.         res.push_back(tmp);
  255.     }
  256.  
  257.     if (r_i % 4 != 3) {
  258.         std::vector<short int> tmp_mat = this->mat;
  259.         std::swap(tmp_mat.at(r_i), tmp_mat.at(r_i + 1));
  260.         P tmp{ tmp_mat, this->step + 1, R, number };
  261.         res.push_back(tmp);
  262.     }
  263.  
  264.     return res;
  265. }
  266.  
  267.  
  268. std::vector<P> DeleteEntryInSecond(std::vector<P> to, std::vector<unsigned long long int> second) {
  269.     std::vector<P> res;
  270.     for (int i = 0; i < to.size(); ++i) {
  271.         bool tmp = true;
  272.         unsigned long long int chesh = to.at(i).hesh();
  273.         for (int j = 0; j < second.size(); ++j) {
  274.             if (chesh == second.at(j)) {
  275.                 tmp = false;
  276.                 break;
  277.             }
  278.         }
  279.         if (tmp == true) res.push_back(to.at(i));
  280.     }
  281.     return res;
  282. }
  283.  
  284.  
  285. int P::ExistenceOfSolutions() {
  286.     int N = 0;
  287.     for (int i = 0; i < 16; ++i)
  288.         if (this->mat.at(i) != 0) {
  289.             for (int z = 0; z < i; ++z)
  290.                 if (mat.at(z) > mat.at(i)) N++;
  291.         }
  292.         else N += i / 4 + 1;
  293.     if (N % 2 != 0) return -1;
  294.     return N;
  295. }
  296.  
  297.  
  298. void alg_A_zvz(P enter) {
  299.     int res = enter.ExistenceOfSolutions();
  300.     if (res == -1) {
  301.         std::cout << res << std::endl;
  302.         return;
  303.     }
  304.  
  305.     std::vector<unsigned long long int>  closed;
  306.     std::vector < std::pair<Sides, short int>>  closed_1;
  307.     Priority_Queue open;
  308.     P current = enter;
  309.     closed.push_back(current.hesh());
  310.     closed_1.push_back(std::make_pair(U, -1));
  311.     open.AddDigit(enter);
  312.  
  313.     std::vector<short int> d;
  314.     for (int i = 0; i < 15; ++i) {
  315.         d.push_back(i + 1);
  316.     }
  317.     d.push_back(0);
  318.     P des{ d, 0, U, -1 };
  319.  
  320.     if (des == current) {
  321.         std::cout << 0 << std::endl;
  322.         return;
  323.     }
  324.     while (!(current.equal(des))) {
  325.         current = open.ExtractMax();
  326.         closed.push_back(current.hesh());
  327.         closed_1.push_back(std::make_pair(current.Side, current.parent));
  328.         std::vector<P> to = DeleteEntryInSecond(current.ReturnNext(closed.size() - 1), closed);
  329.         for (int i = 0; i < to.size(); ++i) {
  330.             open.AddDigit(to.at(i));
  331.         }
  332.  
  333.     }
  334.  
  335.     std::cout << current.step << std::endl;
  336.     int z = closed.size() - 1;
  337.     std::string ress = "";
  338.     while (z != -1) {
  339.         int tmp = closed_1.at(z).first;
  340.         z = closed_1.at(z).second;
  341.         switch (tmp) {
  342.         case 0:
  343.             ress += "D";
  344.             break;
  345.         case 1:
  346.             ress += "U";
  347.             break;
  348.         case 2:
  349.             ress += "R";
  350.             break;
  351.         case 3:
  352.             ress += "L";
  353.             break;
  354.         }
  355.     }
  356.     for (int i = ress.size() - 2; i >= 0; i--) std::cout << ress[i];
  357. }
  358.  
  359.  
  360. int main()
  361. {
  362.     std::vector<short int> ent;
  363.  
  364.     for (int i = 0; i < 16; ++i) {
  365.         short int tmp;
  366.         std::cin >> tmp;
  367.         ent.push_back(tmp);
  368.     }
  369.  
  370.     P enter{ ent, 0, U, -1 };
  371.     //time_t start, end;
  372.     //time(&start);
  373.     alg_A_zvz(enter);
  374.     //time(&end);
  375.     //std::cout << std::endl << "T: " << difftime(end, start) << std::endl;
  376.     system("pause");
  377.     return 0;
  378. }
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top