SHARE
TWEET

Untitled

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