[关闭]
@DingCao-HJJ 2015-10-30T14:46:41.000000Z 字数 7349 阅读 1220

sicily_1151 魔板

sicily

题目

见sicily_1150 简单魔板
仅仅是最大步数可以超过10.

思路

  1. 直接剪枝bfs， 然而很不幸地楼主一直MLE……
  2. 使用康托展开公式来检查一个节点是否已经遍历过。因为能够将n个无重复元素的排列映射到刚好n!个数， 所以可以大大地节省内存。

代码

  1. // Copyright (c) 2015 HuangJunjie@SYSU(SNO:13331087). All Rights Reserved.
  2. // 1151 魔板: http://soj.sysu.edu.cn/1151
  3. #include <cstdio>
  4. #include <cstring>
  5. #include <string>
  6. #include <queue>
  8. using namespace std;
  10. struct Node {
  11.   int state;
  12.   string opt;
  13. };
  15. bool isvisited[40320] = { 0 };
  16. int factor[8] = { 1, 1, 2, 6, 24, 120, 720, 5040 };
  18. Node doA(const Node& node);
  19. Node doB(const Node& node);
  20. Node doC(const Node& node);
  22. int contor(Node current);
  24. int main() {
  25.   int max_steps;
  26.   Node aim;
  28.   Node start;
  29.   start.state = 12348765;
  30.   start.opt = "";
  32.   while (scanf("%d", &max_steps) != EOF && max_steps != -1) {
  33.     int digit;
  34.     aim.state = 0;
  35.     for (int i = 0; i < 8; i++) {
  36.       scanf("%d", &digit);
  37.       aim.state *= 10;
  38.       aim.state += digit;
  39.     }
  41.     memset(isvisited, 0, sizeof(isvisited));
  42.     queue<Node> que;
  43.     que.push(start);
  44.     while (!que.empty()) {
  45.       Node current = que.front();
  46.       que.pop();
  47.       if (isvisited[contor(current)] == true) continue;
  48.       else
  49.         isvisited[contor(current)] = true;
  51.       if (current.opt.size() > max_steps) {
  52.         printf("-1\n");
  53.         break;
  54.       }
  56.       if (contor(current) == contor(aim)) {
  57.         printf("%d %s\n", current.opt.size(), current.opt.c_str());
  58.         break;
  59.       }
  61.       Node Anext = doA(current);
  62.       // if (isvisited[contor(Anext)] == false)
  63.         que.push(Anext);
  64.       Node Bnext = doB(current);
  65.       // if (isvisited[contor(Anext)] == false)
  66.         que.push(Bnext);
  67.       Node Cnext = doC(current);
  68.       // if (isvisited[contor(Anext)] == false)
  69.         que.push(Cnext);
  70.     }
  71.   }
  73.   return 0;
  74. }
  76. Node doA(const Node& node) {
  77.   Node Anext;
  78.   Anext.state = node.state % 10000 * 10000 + node.state / 10000;
  79.   Anext.opt = node.opt + 'A';
  81.   return Anext;
  82. }
  84. Node doB(const Node& node) {
  85.   Node Bnext;
  86.   int up = node.state / 10000;
  87.   int down = node.state % 10000;
  88.   Bnext.state = (up / 10 + up % 10 * 1000) * 10000 + (down / 10 + down % 10 * 1000);
  89.   Bnext.opt = node.opt + 'B';
  91.   return Bnext;
  92. }
  94. Node doC(const Node& node) {
  95.   Node Cnext;
  96.   int fact = 10000000;
  97.   int temp[8];
  98.   for (int i = 0; i < 8; i++) {
  99.     temp[i] = (node.state / fact) % 10;
  100.     fact /= 10;
  101.   }
  103.   Cnext.state = (temp[0] * 1000 + temp[5] * 100 + temp[1] * 10 + temp[3]) * 10000 +
  104.     (temp[4] * 1000 + temp[6] * 100 + temp[2] * 10 + temp[7]);
  105.   Cnext.opt = node.opt + 'C';
  107.   return Cnext;
  108. }
  110. int contor(Node current) {
  111.   int fact = 10000000;
  112.   int temp[8];
  113.   for (int i = 0; i < 8; i++) {
  114.     temp[i] = (current.state / fact) % 10;
  115.     fact /= 10;
  116.   }
  118.   int sum = 0;
  119.   for (int i = 0; i < 8; i++) {
  120.     int count = 0;
  121.     for (int j = i + 1; j < 8; j++) {
  122.       if (temp[i] > temp[j]) count++;
  123.     }
  124.     sum += count*factor[7 - i];
  125.   }
  128.   return sum;
  129. }

优化

将已经遍历过的节点的状态存起来即可，算是小小的优化吧。

  1. // Copyright (c) 2015 HuangJunjie@SYSU(SNO:13331087). All Rights Reserved.
  2. // 1151 魔板: http://soj.sysu.edu.cn/1151
  3. #include <cstdio>
  4. #include <cstring>
  5. #include <string>
  6. #include <queue>
  8. using namespace std;
  10. struct Node {
  11.   int state;
  12.   string opt;
  13. };
  15. bool isvisited[40320] = { 0 };
  16. string opts[40320];         // operation records
  17. int factor[8] = { 1, 1, 2, 6, 24, 120, 720, 5040 };
  19. Node doA(const Node& node);
  20. Node doB(const Node& node);
  21. Node doC(const Node& node);
  23. int contor(Node current);
  25. int main() {
  26.   int max_steps;
  27.   Node aim;
  29.   Node start;
  30.   start.state = 12348765;
  31.   start.opt = "";
  33.   while (scanf("%d", &max_steps) != EOF && max_steps != -1) {
  34.     int digit;
  35.     aim.state = 0;
  36.     for (int i = 0; i < 8; i++) {
  37.       scanf("%d", &digit);
  38.       aim.state *= 10;
  39.       aim.state += digit;
  40.     }
  42.     if (opts[contor(aim)] != "") {
  43.       printf("%d %s\n", opts[contor(aim)].size(), opts[contor(aim)].c_str());
  44.       continue;
  45.     }
  47.     memset(isvisited, 0, sizeof(isvisited));
  48.     queue<Node> que;
  49.     que.push(start);
  50.     while (!que.empty()) {
  51.       Node current = que.front();
  52.       que.pop();
  53.       if (isvisited[contor(current)] == true) {
  54.         continue;
  55.       } else {
  56.         isvisited[contor(current)] = true;
  58.         // stores the operation path.
  59.         if (opts[contor(current)] == "")
  60.           opts[contor(current)] = current.opt;
  61.       }
  62.       if (current.opt.size() > max_steps) {
  63.         printf("-1\n");
  64.         break;
  65.       }
  67.       if (contor(current) == contor(aim)) {
  68.         printf("%d %s\n", current.opt.size(), current.opt.c_str());
  69.         break;
  70.       }
  72.       Node Anext = doA(current);
  73.       que.push(Anext);
  74.       Node Bnext = doB(current);
  75.       que.push(Bnext);
  76.       Node Cnext = doC(current);
  77.       que.push(Cnext);
  78.     }
  79.   }
  81.   return 0;
  82. }
  84. Node doA(const Node& node) {
  85.   Node Anext;
  86.   Anext.state = node.state % 10000 * 10000 + node.state / 10000;
  87.   Anext.opt = node.opt + 'A';
  89.   return Anext;
  90. }
  92. Node doB(const Node& node) {
  93.   Node Bnext;
  94.   int up = node.state / 10000;
  95.   int down = node.state % 10000;
  96.   Bnext.state = (up / 10 + up % 10 * 1000) * 10000 + (down / 10 + down % 10 * 1000);
  97.   Bnext.opt = node.opt + 'B';
  99.   return Bnext;
  100. }
  102. Node doC(const Node& node) {
  103.   Node Cnext;
  104.   int fact = 10000000;
  105.   int temp[8];
  106.   for (int i = 0; i < 8; i++) {
  107.     temp[i] = (node.state / fact) % 10;
  108.     fact /= 10;
  109.   }
  111.   Cnext.state = (temp[0] * 1000 + temp[5] * 100 + temp[1] * 10 + temp[3]) * 10000 +
  112.     (temp[4] * 1000 + temp[6] * 100 + temp[2] * 10 + temp[7]);
  113.   Cnext.opt = node.opt + 'C';
  115.   return Cnext;
  116. }
  118. int contor(Node current) {
  119.   int fact = 10000000;
  120.   int temp[8];
  121.   for (int i = 0; i < 8; i++) {
  122.     temp[i] = (current.state / fact) % 10;
  123.     fact /= 10;
  124.   }
  126.   int sum = 0;
  127.   for (int i = 0; i < 8; i++) {
  128.     int count = 0;
  129.     for (int j = i + 1; j < 8; j++) {
  130.       if (temp[i] > temp[j]) count++;
  131.     }
  132.     sum += count*factor[7 - i];
  133.   }
  135.   return sum;
  136. }

随机样例生成

  1. // Copyright (c) 2015 HuangJunjie@SYSU(SNO:13331087). All Rights Reserved.
  2. #define ALPHA_SIZE 26
  3. #include <iostream>
  4. #include <fstream>
  5. #include <string>
  6. #include <cstring>
  7. #include <ctime>
  9. #include <cstdio>
  10. #include <string>
  11. #include <queue>
  12. #include <vector>
  14. using namespace std;
  16. struct Node {
  17.   int state;
  18.   string opt;
  19. } start;
  21. bool isvisited[40320] = { 0 };
  22. string opts[40320];         // operation records
  23. int factor[8] = { 1, 1, 2, 6, 24, 120, 720, 5040 };
  25. Node doA(const Node& node);
  26. Node doB(const Node& node);
  27. Node doC(const Node& node);
  29. int contor(Node current);
  31. fstream testcase;
  32. fstream answer;
  34. void init();
  35. void makeTestCase(int cases);
  36. void build();
  37. void bfs(Node aim);
  39. Node recontor(int i);
  41. int main() {
  42.   init();
  44.   for (int cases = 10; cases < 10000; cases *= 10) {
  45.     makeTestCase(cases);
  46.   }
  47.   for (int cases = 50; cases < 50000; cases *= 10) {
  48.     makeTestCase(cases);
  49.   }
  51.   return 0;
  52. }
  54. void init() {
  55.   srand(time(NULL));
  56.   start.state = 12348765;
  57.   start.opt = "";
  59.   build();
  60. }
  62. void build() {
  63.   for (int i = 0; i < 40320; i++) {
  64.     if (opts[i] == "") {
  65.       Node aim = recontor(i);
  66.       bfs(aim);
  67.     }
  68.   }
  69. }
  71. void bfs(Node aim) {
  72.   memset(isvisited, 0, sizeof(isvisited));
  73.   queue<Node> que;
  74.   que.push(start);
  75.   while (!que.empty()) {
  76.     Node current = que.front();
  77.     que.pop();
  78.     if (isvisited[contor(current)] == true) {
  79.       continue;
  80.     } else {
  81.       isvisited[contor(current)] = true;
  83.       // stores the operation path.
  84.       if (opts[contor(current)] == "")
  85.         opts[contor(current)] = current.opt;
  86.     }
  88.     if (contor(current) == contor(aim)) {
  89.       return;
  90.     }
  92.     Node Anext = doA(current);
  93.     que.push(Anext);
  94.     Node Bnext = doB(current);
  95.     que.push(Bnext);
  96.     Node Cnext = doC(current);
  97.     que.push(Cnext);
  98.   }
  99. }
  101. void makeTestCase(int cases) {
  102.   char buf[5];
  103.   sprintf(buf, "%d", cases);
  104.   string cases_str = buf;
  105.   string inputname = "input" + cases_str + ".txt";
  106.   string answername = "answer" + cases_str + ".txt";
  107.   testcase.open(inputname, ios::out);
  108.   answer.open(answername, ios::out);
  110.   for (int i = 0; i < cases; i++) {
  111.     int steps = rand() % cases;
  113.     testcase << steps << endl;
  114.     int key = rand() % 40320;
  116.     Node test = recontor(key);
  118.     for (int factor = 10000000; factor; factor /= 10) {
  119.       if (factor != 10000000 && factor != 1000) testcase << " ";
  120.       if (factor == 1000) testcase << endl;
  121.       testcase << test.state / factor;
  122.       test.state %= factor;
  123.     }
  124.     testcase << endl;
  126.     answer << opts[key].size() << " " << opts[key] << endl;
  127.   }
  128.   testcase << -1 << endl;
  130.   testcase.close();
  131.   answer.close();
  132. }
  134. Node doA(const Node& node) {
  135.   Node Anext;
  136.   Anext.state = node.state % 10000 * 10000 + node.state / 10000;
  137.   Anext.opt = node.opt + 'A';
  139.   return Anext;
  140. }
  142. Node doB(const Node& node) {
  143.   Node Bnext;
  144.   int up = node.state / 10000;
  145.   int down = node.state % 10000;
  146.   Bnext.state = (up / 10 + up % 10 * 1000) * 10000 + (down / 10 + down % 10 * 1000);
  147.   Bnext.opt = node.opt + 'B';
  149.   return Bnext;
  150. }
  152. Node doC(const Node& node) {
  153.   Node Cnext;
  154.   int fact = 10000000;
  155.   int temp[8];
  156.   for (int i = 0; i < 8; i++) {
  157.     temp[i] = (node.state / fact) % 10;
  158.     fact /= 10;
  159.   }
  161.   Cnext.state = (temp[0] * 1000 + temp[5] * 100 + temp[1] * 10 + temp[3]) * 10000 +
  162.     (temp[4] * 1000 + temp[6] * 100 + temp[2] * 10 + temp[7]);
  163.   Cnext.opt = node.opt + 'C';
  165.   return Cnext;
  166. }
  168. int contor(Node current) {
  169.   int fact = 10000000;
  170.   int temp[8];
  171.   for (int i = 0; i < 8; i++) {
  172.     temp[i] = (current.state / fact) % 10;
  173.     fact /= 10;
  174.   }
  176.   int sum = 0;
  177.   for (int i = 0; i < 8; i++) {
  178.     int count = 0;
  179.     for (int j = i + 1; j < 8; j++) {
  180.       if (temp[i] > temp[j]) count++;
  181.     }
  182.     sum += count*factor[7 - i];
  183.   }
  185.   return sum;
  186. }
  188. Node recontor(int key) {
  189.   Node result;
  190.   result.state = 0;
  191.   bool num[8] = { 0 };
  192.   for (int i = 7; i >= 0; i--) {
  193.     int count = -1;
  194.     int remain = key / factor[i];
  195.     key %= factor[i];
  196.     for (int j = 0; j < 8; j++) {
  197.       if (num[j] == false) count++;
  198.       if (count == remain) {
  199.         num[j] = true;
  200.         result.state *= 10;
  201.         result.state += j + 1;
  202.         break;
  203.       }
  204.     }
  205.   }
  207.   return result;
  208. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注