fork download
copy 
  1. /*
  2. setter solution
  3.  
  4. Split the warehouse into 5 regions:
  5.  
  6. x333333
  7. 1322222
  8. 1455555
  9. 1455555
  10. 1455555
  11. 1455555
  12. 1455555
  13.  
  14. Ideally, fill in the regions as follows:
  15.  
  16. 1: earliest to drop off shipments
  17. 2: next earliest to drop off shipments
  18. 3: last to pick up shipments
  19. 4: next last to pick up shipments
  20. 5: everything else
  21.  
  22. It's not possible to follow them exactly if there are shipments that are picked
  23. up late and dropped off early, which will be special-cased as needed.
  24.  
  25. Single-character instructions are used, then expanded at the end. Lower case
  26. characters are used in place of load and unload instructions. For example,
  27. "w" is used instead of "LW" or "UW". It is unambiguous because at most one
  28. interpretation is ever valid. See "Expand" function.
  29.  
  30. */
  31.  
  32. #include <cassert>
  33. #include <cctype>
  34. #include <cstdio>
  35. #include <cstring>
  36. #include <algorithm>
  37. #include <string>
  38.  
  39. char Transform(const char* before, const char* after, char c)
  40. {
  41.     const char* pos = strchr(before, c);
  42.     if (!pos)
  43.         return c;
  44.     return after[pos-before];
  45. }
  46.  
  47. // Instruction that does the opposite of the given instruction
  48. char Opposite(char c)
  49. {
  50.     static const char* before = "NWSEPDnwse";
  51.     static const char* after  = "SENWDPnwse";
  52.     return Transform(before, after, c);
  53. }
  54.  
  55. // Find a set of instructions that undo the effects of another set of instructions
  56. std::string Undo(std::string s)
  57. {
  58.     std::transform(s.begin(), s.end(), s.begin(), Opposite);
  59.     std::reverse(s.begin(), s.end());
  60.     return s;
  61. }
  62.  
  63. // Remove adjacent moves that cancel eachother out, such as a "N" followed by a "S"
  64. std::string Annihilate(std::string s)
  65. {
  66.     std::string res;
  67.     for (size_t i = 0; i < s.size(); i++)
  68.     {
  69.         if (!res.empty() && res.back() == Opposite(s[i]))
  70.             res.pop_back();
  71.         else
  72.             res.push_back(s[i]);
  73.     }
  74.     return res;
  75. }
  76.  
  77. // Expand a compact instruction sequence into the format required by the judge
  78. std::string Expand(std::string s)
  79. {
  80.     std::string res;
  81.     bool has = false;
  82.     for (size_t i = 0; i < s.size(); i++)
  83.     {
  84.         if (std::islower(s[i]))
  85.         {
  86.             res.push_back(has ? 'U' : 'L');
  87.             res.push_back(toupper(s[i]));
  88.             has = !has;
  89.         }
  90.         else
  91.         {
  92.             res.push_back(s[i]);
  93.             if (s[i] == 'P' || s[i] == 'D')
  94.                 has = !has;
  95.         }
  96.     }
  97.     return res;
  98. }
  99.  
  100. // Reflect direction across diagonal line
  101. char Transposed(char c)
  102. {
  103.     return Transform("NWSE", "WNES", c);
  104. }
  105.  
  106. // Transform a (expanded) solution with C rows and R columns into one with R rows and C columns
  107. std::string Transpose(std::string s)
  108. {
  109.     std::transform(s.begin(), s.end(), s.begin(), Transposed);
  110.     return s;
  111. }
  112.  
  113. // Assuming the forklift starts at the entrance, find the first shipment it picks up
  114. std::pair<int, int> FirstShipment(std::string route)
  115. {
  116.     int r = 0, c = 0;
  117.     for (char i : route)
  118.     {
  119.         switch (toupper(i))
  120.         {
  121.             case 'N': r--; break;
  122.             case 'S': r++; break;
  123.             case 'W': c--; break;
  124.             case 'E': c++; break;
  125.         }
  126.         if (islower(i))
  127.             break;
  128.     }
  129.     return std::make_pair(r, c);
  130. }
  131.  
  132. // Extract all shipments from the warehouse, in order from 0 to R*C-2
  133. std::string Solve(const int R, const int C, int warehouse[20][20], int phase)
  134. {
  135.     std::string res;
  136.     int len = R*C-1;
  137.     int row[400], col[400];
  138.     for (int r = 0; r < R; r++)
  139.     for (int c = 0; c < C; c++)
  140.     {
  141.         if (r == 0 && c == 0)
  142.             continue;
  143.         row[warehouse[r][c]] = r;
  144.         col[warehouse[r][c]] = c;
  145.     }
  146.     for (int s = 0; s < len; s++)
  147.     {
  148.         while (true)
  149.         {
  150.             // Try a bfs first
  151.             char mark[20][20] = {{}};
  152.             std::pair<int, int> q[400];
  153.             int qfront = 0, qback = 1;
  154.             q[0].first = row[s];
  155.             q[0].second = col[s];
  156.             static const int dr[4] = {-1, 0, 1, 0};
  157.             static const int dc[4] = { 0,-1, 0, 1};
  158.             const char dd[4] = {'N','W','S','E'};
  159.             while (qfront != qback && !mark[0][0])
  160.             {
  161.                 int r = q[qfront].first;
  162.                 int c = q[qfront].second;
  163.                 qfront++;
  164.                 for (int d = 0; d < 4; d++)
  165.                 {
  166.                     int nr = r-dr[d];
  167.                     int nc = c-dc[d];
  168.                     if (!(0 <= nr && nr < R && 0 <= nc && nc < C))
  169.                         continue;
  170.                     if (mark[nr][nc] || warehouse[nr][nc] != -1)
  171.                         continue;
  172.                     mark[nr][nc] = d+1;
  173.                     q[qback].first = nr;
  174.                     q[qback].second = nc;
  175.                     qback++;
  176.                 }
  177.             }
  178.             // Found a path
  179.             if (mark[0][0])
  180.             {
  181.                 std::string route;
  182.                 int r = 0;
  183.                 int c = 0;
  184.                 while (r != row[s] || c != col[s])
  185.                 {
  186.                     int d = mark[r][c]-1;
  187.                     route.push_back(dd[d]);
  188.                     r += dr[d];
  189.                     c += dc[d];
  190.                 }
  191.                 // Ignore paths that waste too many moves
  192.                 int wastedMoves = route.length() - row[s] - col[s];
  193.                 if (wastedMoves == 0 || ((row[s] == 0 || col[s] == 0) && wastedMoves == 2))
  194.                 {
  195.                     // Drop it off
  196.                     char loadDir = tolower(route.back());
  197.                     route.pop_back();
  198.                     res.append(route);
  199.                     res.push_back(loadDir);
  200.                     res.append(Undo(route));
  201.                     res.push_back('D');
  202.                     warehouse[row[s]][col[s]] = -1;
  203.                     break;
  204.                 }
  205.             }
  206.             // Going to need to move something out of the way before trying again.
  207.             std::string route;
  208.             // A bit of trial and error was needed to get all this right
  209.             if (phase == 0)
  210.             {
  211.                 assert(col[s] == 0);
  212.                 assert(warehouse[0][2] == -1);
  213.                 route.push_back('E');
  214.                 route.append(row[s]-1, 'S');
  215.                 route.push_back('s');
  216.                 if (warehouse[1][0] == -1)
  217.                 {
  218.                     route.append(row[s]-2, 'N');
  219.                     route.append("wNW");
  220.                 }
  221.                 else
  222.                 {
  223.                     route.append(row[s]-1, 'N');
  224.                     route.append("eW");
  225.                 }
  226.             }
  227.             else
  228.             {
  229.                 if (row[s] == 0 && col[s] == 2 && warehouse[1][1] == -1)
  230.                     route = "eEsW";
  231.                 else if (col[s] == 1)
  232.                 {
  233.                     if (warehouse[1][0] != -1)
  234.                         route = "se";
  235.                     else
  236.                         route = "SseN";
  237.                 }
  238.                 else if (row[s] == 0)
  239.                 {
  240.                     if (warehouse[1][1] == -1)
  241.                     {
  242.                         route.push_back('S');
  243.                         route.append(col[s]-1, 'E');
  244.                         route.push_back('e');
  245.                         if (warehouse[0][1] == -1)
  246.                         {
  247.                             route.append(col[s]-2, 'W');
  248.                             route.append("nWN");
  249.                         }
  250.                         else
  251.                         {
  252.                             route.append(col[s]-1, 'W');
  253.                             route.append("sN");
  254.                         }
  255.                     }
  256.                     else if (warehouse[0][1] == -1 && warehouse[0][2] == -1)
  257.                     {
  258.                         route = "EES";
  259.                         route.append(col[s]-3, 'E');
  260.                         route.push_back('e');
  261.                         route.append(col[s]-3, 'W');
  262.                         route.append("NWWs");
  263.                     }
  264.                     else
  265.                         route = "SesN";
  266.                 }
  267.                 else if (col[s] == 0)
  268.                     route = "SseN";
  269.                 else
  270.                     route = "SesN";
  271.             }
  272.             res.append(route);
  273.             std::pair<int, int> before = FirstShipment(route);
  274.             std::pair<int, int> after = FirstShipment(Undo(route));
  275.             assert(warehouse[before.first][before.second] != -1);
  276.             assert(warehouse[after.first][after.second] == -1);
  277.             std::swap(warehouse[before.first][before.second], warehouse[after.first][after.second]);
  278.             row[warehouse[after.first][after.second]] = after.first;
  279.             col[warehouse[after.first][after.second]] = after.second;
  280.         }        
  281.     }
  282.     // remove extraneous moves
  283.     return Annihilate(res);
  284. }
  285.  
  286. // GetRoute helper - get last unmarked shipment by arrival order
  287. inline int GetLastUnmarked(bool mark[], const int ord[], int& rpos)
  288. {
  289.     while (mark[ord[rpos]])
  290.         rpos--;
  291.     mark[ord[rpos]] = true;
  292.     return ord[rpos];
  293. }
  294.  
  295. // GetRoute helper - get first unmarked shipment by drop-off order (shipment number)
  296. inline int GetFirstUnmarked(bool mark[], int& next)
  297. {
  298.     while (mark[next])
  299.         next++;
  300.     mark[next] = true;
  301.     return next;
  302. }
  303.  
  304. std::string GetRoute(const int R, const int C, const int ord[])
  305. {
  306.     int len = R*C-1;
  307.     int warehouse[20][20];
  308.     warehouse[0][0] = -1;
  309.     int rpos = len-1;
  310.     bool mark[400] = {};
  311.     bool unmark[400] = {};
  312.  
  313.     // Inverse mapping of given order
  314.     int invOrd[400];
  315.     for (int i = 0; i < len; i++)
  316.         invOrd[ord[i]] = i;
  317.  
  318.     // Smallest number not yet assigned
  319.     int nextSmallest = 0;
  320.     // Last arriving shipment goes at (1,0)
  321.     warehouse[0][1] = GetLastUnmarked(mark, ord, rpos);
  322.     // Shipment 1 goes at (0,1)
  323.     warehouse[1][0] = GetFirstUnmarked(mark, nextSmallest);
  324.     // Reserve late shipments for section 3, the smallest of which will go at (1,1)
  325.     warehouse[1][1] = R*C;
  326.     for (int c = 1; c < C; c++)
  327.     {
  328.         int last = GetLastUnmarked(mark, ord, rpos);
  329.         unmark[last] = true;
  330.         warehouse[1][1] = std::min(warehouse[1][1], last);
  331.         // Having too many small-numbered shipments in section 3 can be
  332.         // problematic, but we can fill it with earlier-arriving shipments in this case
  333.         if (c > 1 && last < R)
  334.         {
  335.             break;
  336.         }
  337.     }
  338.     unmark[warehouse[1][1]] = false;
  339.     // Populate sections 1 and 4
  340.     for (int r = 2; r < R; r++)
  341.     {
  342.         warehouse[r][0] = GetFirstUnmarked(mark, nextSmallest);
  343.         warehouse[r][1] = GetLastUnmarked(mark, ord, rpos);
  344.     }
  345.     // Reset shipments reserved for section 3
  346.     for (int i = 0; i < len; i++)
  347.     {
  348.         if (unmark[i])
  349.             mark[i] = false;
  350.     }
  351.     nextSmallest = 0;
  352.     rpos = len-1;
  353.  
  354.     // Populate sections 2 and 3
  355.     for (int c = 2; c < C; c++)
  356.     {
  357.         warehouse[0][c] = GetLastUnmarked(mark, ord, rpos);
  358.         warehouse[1][c] = GetFirstUnmarked(mark, nextSmallest);
  359.     }
  360.     // Populate section 5. Shipments go into rows based on drop-off order, columns based on pick-up order
  361.     for (int r = 2; r < R; r++)
  362.     {
  363.         std::pair<int, int> shipments[20];
  364.         for (int i = 0; i < C-2; i++)
  365.         {
  366.             shipments[i].second = GetFirstUnmarked(mark, nextSmallest);
  367.             shipments[i].first = -invOrd[shipments[i].second];
  368.         }
  369.         std::sort(shipments, shipments+C-2);
  370.         for (int c = 2; c < C; c++)
  371.         {
  372.             warehouse[r][c] = shipments[c-2].second;
  373.         }
  374.     }
  375.  
  376.     // Renumber for sequential pick up
  377.     int warehouse2[20][20];
  378.     for (int r = 0; r < R; r++)
  379.     for (int c = 0; c < C; c++)
  380.         warehouse2[r][c] = (r == 0 && c == 0) ? -1 : len-1-invOrd[warehouse[r][c]];
  381.  
  382.     // pick up
  383.     std::string part1 = Solve(R, C, warehouse2, 0);
  384.     // drop off
  385.     std::string part2 = Solve(R, C, warehouse, 1);
  386.  
  387.     return Expand(Undo(part1) + part2);
  388. }
  389.  
  390. int main()
  391. {
  392.     int T;
  393.     scanf("%d", &T);
  394.     for (int t = 0; t < T; t++)
  395.     {
  396.         int R, C;
  397.         scanf("%d%d", &R, &C);
  398.         int ord[400];
  399.         int len = R*C-1;
  400.         for (int i = 0; i < len; i++)
  401.         {
  402.             scanf("%d", ord+i);
  403.             ord[i]--;
  404.         }
  405.         std::string route = GetRoute(R, C, ord);
  406.         if (R != C)
  407.         {
  408.             std::string route2 = GetRoute(C, R, ord);
  409.             if (route2.length() < route.length())
  410.                 route = Transpose(route2);
  411.         }
  412.         printf("%s\n", route.c_str());
  413.     }
  414. }
Success #stdin #stdout 0s 4356KB
comments (?)
stdin
copy 
1
7 8
40 23 17 1 47 27 43 36 16 49 24 39 30 7 38 51 21 3 35 2 52 28 5 20 53 8 18 44 4 45 14 55 10 22 42 6 31 11 41 15 25 29 26 46 50 33 32 37 54 13 34 9 48 12 19
stdout
copy 
PEEEEEEESSSSUSNNNNWWWWWWWPEEEEEEESSUSNNWWWWWWWPEEEEEEESUSNWWWWWWWPUSPEEEEEESSSSSSUENNNNNNWWWWWWPEEEEEESSUSNNWWWWWWPEEEEESSSSEUSWNNNNWWWWWPEEEEESSSSEUEWNNNNWWWWWPEEEEEESUSNWWWWWWPEEEEESSSSSSUENNNNNNWWWWWPEEEEESSUSNNWWWWWPEEEESSSSEUEWNNNNWWWWPEEEESSSSUENNNNWWWWPEEUSWWPEEEESSSUSNNNWWWWPEEESSSSSEEUSWWNNNNNWWWPEEEEESUSNWWWWWPESSSUWNNNWPEEESSSUSNNNWWWPESSUWNNWPESSESSSEEUSWWNNNWNNWPEEEESSUSNNWWWWPESSSSSUWNNNNNWPEEEESUSNWWWWPESSESSSEUSWNNNWNNWPEEEUSWWWPESSEUEWNNWPESSESSSEEUEWWNNNWNNWPESSSSUWNNNNWPESSESSSEUEWNNNWNNWPEEEEEEUSWWWWWWPESSESSSUSNNNWNNWPEEEEUSWWWWPESSUENNWPESSSESSUENNWNNNWPESSSSSSUWNNNNNNWPESSSEUSWNNNWPEEEEEUSWWWWWPESSSSSUENNNNNWPEEEEEEEUSWWWWWWWPESSSEUEWNNNWPESSSUENNNWPESSSSSUSNNNNNWPESSSSUSNNNNWPESSSUSNNNWPESSUSNNWPESUSNWPEEEEEEUEWWWWWWPEEEEEUEWWWWWPEEEEUEWWWWPEEEUEWWWPEUSWPEEUEWWPEUEWPUELSDSLSNDSSLSNNDSSSLSNNNDSSSSLSNNNNDSSSSSLSNNNNNDSLEUSELEWNDSEELEWWNDSLSNDSEEELEWWWNDSEEEELEWWWWNDSEELNWWNDSEEEEELNWWWWWNDSEEEEELEWWWWWNDSEEEEEELEWWWWWWNDSEEEEEELSWWWWWWNDSEEEEEEELSWWWWWWWNDSEEELSWWWNDLEDEESEELSWWNWWDEESEEELSWWWNWWDEESLSNWWDEESEEEEESLSNWWWWWNWWDEESEEESLSNWWWNWWDEESESLSNWNWWDSSSSSSLENNNNNNDEESEEEESLSNWWWWNWWDEESEESLSNWWNWWDEESSLSNNWWDEESEEESSLSNNWWWNWWDEESSSLSNNNWWDESLSNWDESSLSNNWDEESEELNWWNWWDEESESSLSNNWNWWDEESEEEEESSLSNNWWWWWNWWDEESEEEEELNWWWWWNWWDEESEESSLSNNWWNWWDEESEEEESSLSNNWWWWNWWDEESEEEEESSSLSNNNWWWWWNWWDEESSSSLSNNNNWWDEESESSSLSNNNWNWWDEESEEEESSSLSNNNWWWWNWWDEESEEESSSLSNNNWWWNWWDEESEESSSLSNNNWWNWWDSSSSSLENNNNNDEESEEEEESSSSLSNNNNWWWWWNWWDEELEWWDEEEEESESSSSLSNNNNWNWWWWWDESSSLSNNNWDEEEEESSSSSLSNNNNNWWWWWDEEEESSSSSLSNNNNNWWWWDEEESSSSSLSNNNNNWWWDEEEEELEWWWWWDEESSSSSLSNNNNNWWD
https://ideone.com/tzPq4b
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!