API tools faq
paste
Advertisement
MystMe

Untitled

MystMe
Mar 28th, 2018
71
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 11.68 KB | None | 0 0
raw download clone embed print report
  1. // B
  2. //time:444.431s
  3. //memory: 380.00Kb
  4.  
  5. #define DONE 1147797409030816545
  6. #include <sstream>
  7. #include <iostream>
  8. #include <queue>
  9. using namespace std;
  10.  
  11. const unsigned long long Masks[] = {
  12.         0x000000000000000F,
  13.         0x00000000000000F0,
  14.         0x0000000000000F00,
  15.         0x000000000000F000,
  16.         0x00000000000F0000,
  17.         0x0000000000F00000,
  18.         0x000000000F000000,
  19.         0x00000000F0000000,
  20.         0x0000000F00000000,
  21.         0x000000F000000000,
  22.         0x00000F0000000000,
  23.         0x0000F00000000000,
  24.         0x000F000000000000,
  25.         0x00F0000000000000,
  26.         0x0F00000000000000,
  27.         0xF000000000000000,
  28. };
  29. const unsigned long long AntiMasks[] = {
  30.         0xFFFFFFFFFFFFFFF0,
  31.         0xFFFFFFFFFFFFFF0F,
  32.         0xFFFFFFFFFFFFF0FF,
  33.         0xFFFFFFFFFFFF0FFF,
  34.         0xFFFFFFFFFFF0FFFF,
  35.         0xFFFFFFFFFF0FFFFF,
  36.         0xFFFFFFFFF0FFFFFF,
  37.         0xFFFFFFFF0FFFFFFF,
  38.         0xFFFFFFF0FFFFFFFF,
  39.         0xFFFFFF0FFFFFFFFF,
  40.         0xFFFFF0FFFFFFFFFF,
  41.         0xFFFF0FFFFFFFFFFF,
  42.         0xFFF0FFFFFFFFFFFF,
  43.         0xFF0FFFFFFFFFFFFF,
  44.         0xF0FFFFFFFFFFFFFF,
  45.         0x0FFFFFFFFFFFFFFF
  46. };
  47. struct Element{
  48.     unsigned long long data; // sequence
  49.     string Prev; // Prev;
  50.     unsigned long long Dist;
  51.  
  52.     unsigned long long Father;
  53.     Element(string P): Prev(P), Dist(0), Father(0) {}
  54.  
  55.     void setAt( int place, unsigned char value )
  56.     {
  57.         data = ( data & AntiMasks[place] ) | ( static_cast<long long>( value ) << ( place << 2 ) );
  58.     }
  59.  
  60.     unsigned char getAt( int place ) const
  61.     {
  62.         return static_cast<unsigned char>( ( data & Masks[place] ) >> ( place << 2 ) );
  63.     }
  64.     unsigned long long H(){
  65.         unsigned long long h = 0;
  66.         for(int i = 0; i<16; i++){
  67.             char value = getAt(i);
  68.             if(value != 0){
  69.                 int targetX = (value - 1) / 4; // expected x-coordinate (row)
  70.                 int targetY = (value - 1) % 4; // expected y-coordinate (col)
  71.                 int dx = i/4 - targetX; // x-distance to expected coordinate
  72.                 int dy = i%4 - targetY; // y-distance to expected coordinate
  73.                 h += (abs(dx) + abs(dy));
  74.             }
  75.         }
  76.         return h;
  77.     }
  78.     void F(){
  79.         Dist = Prev.size()+H();
  80.     }
  81. };
  82.  
  83. Element MoveRight(Element l, int pos){
  84.     l.Father = l.data;
  85.     unsigned char k = l.getAt(pos+1);
  86.     l.setAt(pos,k);
  87.     l.setAt(pos+1,0);
  88.  
  89.     l.Prev = l.Prev +'L';
  90.     l.F();
  91.     return l;
  92. }
  93. Element MoveLeft(Element l, int pos){
  94.     l.Father = l.data;
  95.     unsigned char k = l.getAt(pos-1);
  96.     l.setAt(pos, k);
  97.     l.setAt(pos-1,0);
  98.  
  99.     l.Prev = l.Prev +'R';
  100.     l.F();
  101.     return l;
  102. }
  103. Element MoveUp(Element l, int pos){
  104.     l.Father = l.data;
  105.     unsigned char k = l.getAt(pos-4);
  106.     l.setAt(pos, k);
  107.     l.setAt(pos-4,0);
  108.  
  109.     l.Prev = l.Prev +'D';
  110.     l.F();
  111.     return l;
  112. }
  113. Element MoveDown(Element l, int pos){
  114.     l.Father = l.data;
  115.     unsigned char k = l.getAt(pos+4);
  116.     l.setAt(pos,k);
  117.     l.setAt(pos+4,0);
  118.  
  119.     l.Prev = l.Prev +'U';
  120.     l.F();
  121.     return l;
  122. }
  123.  
  124. vector<Element> getNodes(Element tmp){
  125.     vector<Element> ToReturn;
  126.     if(tmp.getAt(0) == 0){
  127.         Element toPush = MoveRight(tmp,0);
  128.         if(tmp.Father != toPush.data){
  129.             ToReturn.push_back(toPush);
  130.         }
  131.  
  132.         toPush = MoveDown(tmp,0);
  133.         if(tmp.Father != toPush.data){
  134.             ToReturn.push_back(toPush);
  135.         }
  136.     }
  137.     else if(tmp.getAt(1) == 0){
  138.         Element toPush = MoveRight(tmp,1);
  139.         if(tmp.Father != toPush.data){
  140.             ToReturn.push_back(toPush);
  141.         }
  142.  
  143.         toPush = MoveDown(tmp,1);
  144.         if(tmp.Father != toPush.data){
  145.             ToReturn.push_back(toPush);
  146.         }
  147.  
  148.         toPush = MoveLeft(tmp,1);
  149.         if(tmp.Father != toPush.data){
  150.             ToReturn.push_back(toPush);
  151.         }
  152.     }
  153.     else if(tmp.getAt(2) == 0){
  154.  
  155.         Element toPush = MoveRight(tmp,2);
  156.         if(tmp.Father != toPush.data){
  157.             ToReturn.push_back(toPush);
  158.         }
  159.  
  160.         toPush = MoveDown(tmp,2);
  161.         if(tmp.Father != toPush.data){
  162.             ToReturn.push_back(toPush);
  163.         }
  164.  
  165.         toPush = MoveLeft(tmp,2);
  166.         if(tmp.Father != toPush.data){
  167.             ToReturn.push_back(toPush);
  168.         }
  169.     }
  170.     else if(tmp.getAt(3) == 0){
  171.         Element toPush = MoveLeft(tmp,3);
  172.         if(tmp.Father != toPush.data){
  173.             ToReturn.push_back(toPush);
  174.         }
  175.  
  176.         toPush = MoveDown(tmp,3);
  177.         if(tmp.Father != toPush.data){
  178.             ToReturn.push_back(toPush);
  179.         }
  180.     }
  181.     else if(tmp.getAt(4) == 0){
  182.         Element toPush = MoveRight(tmp,4);
  183.         if(tmp.Father != toPush.data){
  184.             ToReturn.push_back(toPush);
  185.         }
  186.  
  187.         toPush = MoveDown(tmp,4);
  188.         if(tmp.Father != toPush.data){
  189.             ToReturn.push_back(toPush);
  190.         }
  191.  
  192.         toPush = MoveUp(tmp,4);
  193.         if(tmp.Father != toPush.data){
  194.             ToReturn.push_back(toPush);
  195.         }
  196.     }
  197.     else if(tmp.getAt(5) == 0){
  198.  
  199.         Element toPush = MoveRight(tmp,5);
  200.         if(tmp.Father != toPush.data){
  201.             ToReturn.push_back(toPush);
  202.         }
  203.  
  204.         toPush = MoveLeft(tmp,5);
  205.         if(tmp.Father != toPush.data){
  206.             ToReturn.push_back(toPush);
  207.         }
  208.  
  209.         toPush = MoveDown(tmp,5);
  210.         if(tmp.Father != toPush.data){
  211.             ToReturn.push_back(toPush);
  212.         }
  213.  
  214.         toPush = MoveUp(tmp,5);
  215.         if(tmp.Father != toPush.data){
  216.             ToReturn.push_back(toPush);
  217.         }
  218.     }
  219.     else if(tmp.getAt(6) == 0){
  220.  
  221.         Element toPush = MoveRight(tmp,6);
  222.         if(tmp.Father != toPush.data){
  223.             ToReturn.push_back(toPush);
  224.         }
  225.  
  226.         toPush = MoveLeft(tmp,6);
  227.         if(tmp.Father != toPush.data){
  228.             ToReturn.push_back(toPush);
  229.         }
  230.  
  231.         toPush = MoveDown(tmp,6);
  232.         if(tmp.Father != toPush.data){
  233.             ToReturn.push_back(toPush);
  234.         }
  235.  
  236.         toPush = MoveUp(tmp,6);
  237.         if(tmp.Father != toPush.data){
  238.             ToReturn.push_back(toPush);
  239.         }
  240.     }
  241.     else if(tmp.getAt(7) == 0){
  242.  
  243.         Element toPush = MoveLeft(tmp,7);
  244.         if(tmp.Father != toPush.data){
  245.             ToReturn.push_back(toPush);
  246.         }
  247.  
  248.         toPush = MoveDown(tmp,7);
  249.         if(tmp.Father != toPush.data){
  250.             ToReturn.push_back(toPush);
  251.         }
  252.  
  253.         toPush = MoveUp(tmp,7);
  254.         if(tmp.Father != toPush.data){
  255.             ToReturn.push_back(toPush);
  256.         }
  257.     }
  258.     else if(tmp.getAt(8) == 0){
  259.  
  260.         Element toPush = MoveRight(tmp,8);
  261.         if(tmp.Father != toPush.data){
  262.             ToReturn.push_back(toPush);
  263.         }
  264.  
  265.         toPush = MoveDown(tmp,8);
  266.         if(tmp.Father != toPush.data){
  267.             ToReturn.push_back(toPush);
  268.         }
  269.  
  270.         toPush = MoveUp(tmp,8);
  271.         if(tmp.Father != toPush.data){
  272.             ToReturn.push_back(toPush);
  273.         }
  274.     }
  275.     else if(tmp.getAt(9) == 0){
  276.  
  277.         Element toPush = MoveRight(tmp,9);
  278.         if(tmp.Father != toPush.data){
  279.             ToReturn.push_back(toPush);
  280.         }
  281.  
  282.         toPush = MoveLeft(tmp,9);
  283.         if(tmp.Father != toPush.data){
  284.             ToReturn.push_back(toPush);
  285.         }
  286.  
  287.         toPush = MoveDown(tmp,9);
  288.         if(tmp.Father != toPush.data){
  289.             ToReturn.push_back(toPush);
  290.         }
  291.  
  292.         toPush = MoveUp(tmp,9);
  293.         if(tmp.Father != toPush.data){
  294.             ToReturn.push_back(toPush);
  295.         }
  296.     }
  297.     else if(tmp.getAt(10) == 0){
  298.  
  299.         Element toPush = MoveRight(tmp,10);
  300.         if(tmp.Father != toPush.data){
  301.             ToReturn.push_back(toPush);
  302.         }
  303.  
  304.         toPush = MoveLeft(tmp,10);
  305.         if(tmp.Father != toPush.data){
  306.             ToReturn.push_back(toPush);
  307.         }
  308.  
  309.         toPush = MoveDown(tmp,10);
  310.         if(tmp.Father != toPush.data){
  311.             ToReturn.push_back(toPush);
  312.         }
  313.  
  314.         toPush = MoveUp(tmp,10);
  315.         if(tmp.Father != toPush.data){
  316.             ToReturn.push_back(toPush);
  317.         }
  318.     }
  319.     else if(tmp.getAt(11) == 0){
  320.  
  321.         Element toPush = MoveLeft(tmp,11);
  322.         if(tmp.Father != toPush.data){
  323.             ToReturn.push_back(toPush);
  324.         }
  325.  
  326.         toPush = MoveDown(tmp,11);
  327.         if(tmp.Father != toPush.data){
  328.             ToReturn.push_back(toPush);
  329.         }
  330.  
  331.         toPush = MoveUp(tmp,11);
  332.         if(tmp.Father != toPush.data){
  333.             ToReturn.push_back(toPush);
  334.         }
  335.     }
  336.     else if(tmp.getAt(12) == 0){
  337.  
  338.         Element toPush = MoveRight(tmp,12);
  339.         if(tmp.Father != toPush.data){
  340.             ToReturn.push_back(toPush);
  341.         }
  342.  
  343.         toPush = MoveUp(tmp,12);
  344.         if(tmp.Father != toPush.data){
  345.             ToReturn.push_back(toPush);
  346.         }
  347.     }
  348.     else if(tmp.getAt(13) == 0){
  349.  
  350.         Element toPush = MoveRight(tmp,13);
  351.         if(tmp.Father != toPush.data){
  352.             ToReturn.push_back(toPush);
  353.         }
  354.  
  355.         toPush = MoveLeft(tmp,13);
  356.         if(tmp.Father != toPush.data){
  357.             ToReturn.push_back(toPush);
  358.         }
  359.  
  360.         toPush = MoveUp(tmp,13);
  361.         if(tmp.Father != toPush.data){
  362.             ToReturn.push_back(toPush);
  363.         }
  364.     }
  365.     else if(tmp.getAt(14) == 0){
  366.  
  367.         Element toPush = MoveRight(tmp,14);
  368.         if(tmp.Father != toPush.data){
  369.             ToReturn.push_back(toPush);
  370.         }
  371.  
  372.         toPush = MoveLeft(tmp,14);
  373.         if(tmp.Father != toPush.data){
  374.             ToReturn.push_back(toPush);
  375.         }
  376.  
  377.         toPush = MoveUp(tmp,14);
  378.         if(tmp.Father != toPush.data){
  379.             ToReturn.push_back(toPush);
  380.         }
  381.     }
  382.     else if(tmp.getAt(15) == 0){
  383.  
  384.         Element toPush = MoveLeft(tmp,15);
  385.         if(tmp.Father != toPush.data){
  386.             ToReturn.push_back(toPush);
  387.         }
  388.  
  389.         toPush = MoveUp(tmp,15);
  390.         if(tmp.Father != toPush.data){
  391.             ToReturn.push_back(toPush);
  392.         }
  393.     }
  394.     return ToReturn;
  395. }
  396.  
  397. Element Search(Element node,unsigned long long bound){
  398.     if(node.Dist > bound){
  399.         return node;
  400.     }
  401.     if(node.data == DONE) {
  402.         return node;
  403.     }
  404.     Element min("");
  405.     min.Dist = 100000000;
  406.     vector<Element> vert = getNodes(node);
  407.     for(int i = 0; i < vert.size();i++){
  408.         Element tmp = Search(vert[i], bound);
  409.         if(tmp.data == DONE){
  410.             return tmp;
  411.         }
  412.         if(tmp.Dist < min.Dist){
  413.             min = tmp;
  414.         }
  415.     }
  416.     return min;
  417. }
  418.  
  419. int main(){
  420.     Element start("");
  421.     int ZeroPos = 0;
  422.     for(int i = 0;i < 16;i++){
  423.         int Input;
  424.         cin >> Input;
  425.         start.setAt(i, Input);
  426.         if(Input == 0){
  427.             ZeroPos = i/4;
  428.         }
  429.     }
  430.  
  431.     int mistakes = ZeroPos+1; //Переменная для подсчета счетности
  432.     for(int i = 0;i < 16;i++){
  433.         for(int j = i+1;j<16;j++){
  434.             int f1 = i/4;
  435.             int f2 = i%4;
  436.             int s1 = j/4;
  437.             int s2 = j%4;
  438.  
  439.             int first = start.getAt(f1*4+f2);
  440.             int second = start.getAt(s1*4+s2);
  441.             if(first!= 0 && second != 0){
  442.                 if(first>second){
  443.                     mistakes++;
  444.                 }
  445.             }
  446.         }
  447.     }
  448.     if(mistakes%2 !=0){
  449.         cout << "-1";
  450.         return 0;
  451.     }
  452.     // ^ Проверели решаются ли пятнашки
  453.  
  454.     start.F();
  455.     unsigned long long bound = start.Dist;
  456.     while(1){
  457.         Element tmp = Search(start, bound);
  458.         if(tmp.data == DONE) {
  459.             cout << tmp.Prev.length();
  460.             cout << "\n";
  461.             cout << tmp.Prev;
  462.             return 0;
  463.         }
  464.         bound = tmp.Dist;
  465.     }
  466. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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!