최종 최적화 코드 주소:https://github.com/laiy/Datastructure-Algorithm/blob/master/sicily/1151.c

제목은 다음과 같다.

Constraints

Time Limit: 1 secs, Memory Limit: 32 MB , Special Judge

Description

 
마판은 8개의 크기가 같은 네모난 블록으로 구성되어 있으며, 각각 다른 색깔을 발라 1부터 8까지의 숫자로 표시한다.
초기 상태는
1 2 3 4
8 7 6 5
마판에 대해 세 가지 기본 조작을 할 수 있습니다.
A 작업(상하행 교환):
8 7 6 5
1 2 3 4
B 작업(한 번에 한 행씩 오른쪽으로 이동):
4 1 2 3
5 8 7 6
C 작업(가운데 네 개의 작은 블록이 시계 방향으로 한 칸 회전):
1 7 2 4
8 6 3 5
상술한 세 가지 기본 조작으로 어떤 상태를 다른 상태로 바꿀 수 있다.
 

Input

 
여러 개의 요구 사항을 포함하는 마판을 입력하고 각 마판은 세 줄로 설명합니다.
첫 번째 행은 최대 허용 단계 수를 나타내는 N(10을 초과하지 않는 정수)입니다.
둘째, 세 번째 줄은 목표 상태를 표시하고 마판의 모양에 따라 색깔은 1부터 8까지 표시한다.
N이 -1과 같으면 입력이 끝난 것을 나타낸다.
 

Output

 
모든 마판에 대해 한 줄을 출력합니다.
먼저 해답을 찾으려면 필요한 걸음걸이를 나타내는 정수 M이다.몇 개의 공백이 이어지면 첫 번째 단계부터 A, B 또는 C의 M단계 작업이 순서대로 나옵니다(각 단계는 A, B 또는 C). 두 작업 사이에 공백이 없습니다.
참고: 도달할 수 없으면 M 출력 -1이 됩니다.
 

Sample Input

4
5 8 7 6
4 1 2 3
3
8 7 6 5
1 2 3 4
-1

Sample Output

2 AB
1 A

  ：M  N               。

Problem Source

ZSUACM Team Member
 
이 문제는 난이도가 높지 않은데 중요한 것은 어떻게 최적화하고 더욱 빠르고 효율적이며 메모리를 더 적게 사용하는가이다.
처음에는 이 문제를 보았는데, 전형적인 검색 문제였다.
평범하게 다음과 같은 BFS 검색 코드를 쓸 생각은 없습니다.

  1 #include <cstdio>
  2 #include <string>
  3 #include <iostream>
  4 #include <set>
  5 #include <queue>
  6 
  7 int n, destination, top, bottom, a, b, c, d;
  8 std::string ans;
  9 std::set<int> visited;
 10 
 11 struct State {
 12     int state;
 13     std::string step;
 14     State(int state, std::string step) {
 15         this->state = state;
 16         this->step = step;
 17     }
 18 };
 19 
 20 int OP_A(int state) {
 21     return state / 10000 + state % 10000 * 10000;
 22 }
 23 
 24 int OP_B(int state) {
 25     top = state / 10000;
 26     bottom = state % 10000;
 27     top = top % 10 * 1000 + top / 10;
 28     bottom = bottom % 10 * 1000 + bottom / 10;
 29     return top * 10000 + bottom;
 30 }
 31 
 32 int OP_C(int state) {
 33     a = state / 1000000 % 10;
 34     b = state / 100000 % 10;
 35     c = state / 100 % 10;
 36     d = state / 10 % 10;
 37 
 38     state -= a * 1000000;
 39     state -= b * 100000;
 40     state -= c * 100;
 41     state -= d * 10;
 42 
 43     state += c * 1000000;
 44     state += a * 100000;
 45     state += d * 100;
 46     state += b * 10;
 47 
 48     return state;
 49 }
 50 
 51 void bfs() {
 52     int state = 12348765;
 53     if (state == destination) {
 54         ans = "";
 55         return;
 56     }
 57 
 58     std::queue<State> q;
 59     q.push(State(state, ""));
 60     while (!q.empty()) {
 61         State s = q.front();
 62         q.pop();
 63 
 64         if (visited.find(s.state) != visited.end())
 65             continue;
 66         if (s.step.length() > (size_t)n)
 67             break;
 68         if (s.state == destination) {
 69             ans = s.step;
 70             break;
 71         }
 72 
 73         visited.insert(s.state);
 74 
 75         q.push(State(OP_A(s.state), s.step + "A"));
 76         q.push(State(OP_B(s.state), s.step + "B"));
 77         q.push(State(OP_C(s.state), s.step + "C"));
 78     }
 79 }
 80 
 81 int main() {
 82     while (scanf("%d", &n) && n != -1) {
 83 
 84         ans = "NOT FOUND";
 85         destination = 0;
 86         visited.clear();
 87 
 88         int temp[8], base = 1, i;
 89         for (i = 0; i < 8; i++)
 90             scanf("%d", temp + i);
 91         for (i = 7; i >= 0; i--)
 92             destination += temp[i] * base, base *= 10;
 93 
 94         bfs();
 95 
 96         if (ans == "NOT FOUND")
 97             printf("-1
");
 98         else
 99             std::cout << ans.length() << " " << ans << std::endl;
100     }
101     return 0;
102 }

시간 0.4s, 메모리 2300kb.
시간이 현저히 느린 것은 참을 수 없다. 랭킹을 보는 소수의 사람은 0.00s가 가장 좋다!
최적화 프로세스를 시작합니다.
먼저 여기에서 사용한 set 데이터 구조로 검색에서 방문한 노드를 기록하고 우리가 set에 대한 사용은 기본적으로 교집합의 조작과 관련이 없고 단순히 이 요소에 접근하는 것이 존재하지 않는다는 것을 연상할 수 있다.
그러면 주의해야 할 기초 상식이 있다. STL에서 set은 붉은 나무와 검은 나무로 이루어진 것이다. 이때 원소에 대한 검색은 해시보다 훨씬 빠르기 때문에 우리는 set을hash 로 바꾼다.set은 효율을 대폭 높일 것입니다.
즉 원래의 set 성명을hash 로 변경합니다set을 사용하여 다음을 수행할 수 있습니다.

1 __gnu_cxx::hash_set<int> visited;

간단한 변경, 시간 0.25s, 메모리 2428kb.
아직 빠르지 않아!
그래서 계속 수정,hash 포기set,visited수 그룹의 선형 접근으로 변경하지만 메모리가 폭발합니다!8^8의 공간!
콘토르로 펼치면 기록 공간을 줄인다. 즉, 8^8 공간을 8로 눌러라!공간 크기, 이 때 메모리가 터지지 않습니다.
코드는 다음과 같습니다.

  1 #include <cstdio>
  2 #include <string>
  3 #include <iostream>
  4 #include <queue>
  5 #include <cstring>
  6 
  7 int n, destination, top, bottom, a, b, c, d, base, i, j;
  8 std::string ans;
  9 int fact[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};
 10 bool visited[40321];
 11 
 12 struct State {
 13     int state;
 14     std::string step;
 15     State(int state, std::string step) {
 16         this->state = state;
 17         this->step = step;
 18     }
 19 };
 20 
 21 int encode(int n)
 22 {
 23     static int tmp[8];
 24     for (i = 7; i >= 0; i--) {
 25         tmp[i] = n % 10;
 26         n /= 10;
 27     }
 28 
 29     for (i = 0; i < 8; i++) {
 30         base = 0;
 31         for (j = i + 1; j < 8; j++)
 32             if (tmp[i] > tmp[j]) base++;
 33         n += fact[7 - i] * base;
 34     }
 35 
 36     return n;
 37 }
 38 
 39 int OP_A(int state) {
 40     return state / 10000 + state % 10000 * 10000;
 41 }
 42 
 43 int OP_B(int state) {
 44     top = state / 10000;
 45     bottom = state % 10000;
 46     top = top % 10 * 1000 + top / 10;
 47     bottom = bottom % 10 * 1000 + bottom / 10;
 48     return top * 10000 + bottom;
 49 }
 50 
 51 int OP_C(int state) {
 52     a = state / 1000000 % 10;
 53     b = state / 100000 % 10;
 54     c = state / 100 % 10;
 55     d = state / 10 % 10;
 56 
 57     state -= a * 1000000;
 58     state -= b * 100000;
 59     state -= c * 100;
 60     state -= d * 10;
 61 
 62     state += c * 1000000;
 63     state += a * 100000;
 64     state += d * 100;
 65     state += b * 10;
 66 
 67     return state;
 68 }
 69 
 70 void bfs() {
 71     int state = 12348765;
 72     if (state == destination) {
 73         ans = "";
 74         return;
 75     }
 76 
 77     std::queue<State> q;
 78     q.push(State(state, ""));
 79     while (!q.empty()) {
 80         State s = q.front();
 81         q.pop();
 82 
 83         if (visited[encode(s.state)])
 84             continue;
 85         if (s.step.length() > (size_t)n)
 86             break;
 87         if (s.state == destination) {
 88             ans = s.step;
 89             break;
 90         }
 91 
 92         visited[encode(s.state)] = true;
 93 
 94         q.push(State(OP_A(s.state), s.step + "A"));
 95         q.push(State(OP_B(s.state), s.step + "B"));
 96         q.push(State(OP_C(s.state), s.step + "C"));
 97     }
 98 }
 99 
100 int main() {
101     while (scanf("%d", &n) && n != -1) {
102 
103         ans = "NOT FOUND";
104         destination = 0;
105         memset(visited, 0, sizeof(visited));
106 
107         int temp[8], base = 1, i;
108         for (i = 0; i < 8; i++)
109             scanf("%d", temp + i);
110         for (i = 7; i >= 0; i--)
111             destination += temp[i] * base, base *= 10;
112 
113         bfs();
114 
115         if (ans == "NOT FOUND")
116             printf("-1
");
117         else
118             std::cout << ans.length() << " " << ans << std::endl;
119     }
120     return 0;
121 }

시간 0.22s, 공간 1404kb.
효과가hash 보다set 얼마나 빠른가!
그럼 문제는 어디에서 나올까요?
블로거는 하루(수업을 하면서 생각하며) 생각하고 답을 생각했다.
모든 사례가 같은 나무를 검색하고 있습니다!!!!
이렇게 하면 대량의 중복 검색이 발생할 수 있는데, 서로 다른 사례 사이, 특히 테스트 케이스가 많은 상황에서 이것은 불필요한 것이다.
그래서 우리는 나무 전체를 기록해야 한다.
다시 한 번 우리의 데이터 구조를 보면 이전에 사용한 정수로 하나의 노드 상태를 저장했지만 여기서 ABC를 조작하는 효율은 낮다. 우리는 3자리로 숫자를 저장하는 것이 낫다. 이렇게 하면 ABC 조작은 직접 비트 연산으로 완성된다.
그리고 검색 트리를 한 번만 훑어보고 각 노드에 대응하는 조작을 기록한 다음에 구체적으로 필요할 때 역방향 출력을 거슬러 올라가면 결과가 된다. 여기서 수조로 노드 상태를 기록하면 메모리 비용이 너무 크다는 것을 감안하면 1<<24의 크기는 작은 숫자가 아니기 때문에hash맵으로 트리를 기록합니다.
코드는 다음과 같습니다.

 1 #include <cstdio>
 2 #include <queue>
 3 #include <hash_map>
 4 
 5 inline int OP_A(int &n) {
 6     return (n & 4095) << 12 | n >> 12;
 7 }
 8 
 9 inline int OP_B(int &n) {
10     return (( 7 << 9 | 7 << 21 ) & n) >> 9 | (~(7 << 9 | 7 << 21) & n) << 3;
11 }
12 
13 inline int OP_C(int &n) {
14     return ((7 | 7 << 9 | 7 << 12 | 7 << 21) & n) | ((7 << 3) & n) << 3 | ((7 << 6) & n) << 12 | ((7 << 15) & n) >> 12 | ((7 << 18) & n) >> 3;
15 }
16 
17 inline int resume_B(int &n) {
18     return ((7 | 7 << 12) & n) << 9 | (~(7 | 7 << 12) & n) >> 3;
19 }
20 
21 inline int resume_C(int &n) {
22     return ((7 | 7 << 9 | 7 << 12 | 7 << 21) & n) | ((7 << 3) & n) << 12 | ((7 << 6) & n) >> 3 | ((7 << 15) & n) << 3 | ((7 << 18) & n) >> 12;
23 }
24 
25 inline int zip(int *a) {
26     static int code;
27     code = 0;
28     for (int i = 0; i < 8; ++i)
29         code |= (a[i] - 1) << (3 * i);
30     return  code;
31 }
32 
33 int a[] = {1, 2, 3, 4, 8, 7, 6, 5}, origin = zip(a);
34 
35 __gnu_cxx::hash_map<int, char> record;
36 
37 void bfs() {
38     int temp, code;
39     std::queue<int> q;
40     q.push(origin);
41     while (!q.empty()) {
42         code = q.front();
43         q.pop();
44         temp = OP_A(code);
45         if (!record[temp])
46             record[temp] = 'A', q.push(temp);
47         temp = OP_B(code);
48         if (!record[temp])
49             record[temp] = 'B', q.push(temp);
50         temp = OP_C(code);
51         if (!record[temp])
52             record[temp] = 'C', q.push(temp);
53     }
54 }
55 
56 int main() {
57     bfs();
58     int n, arr[8], i, j;
59     char s[30];
60     while (scanf("%d", &n) && n != -1) {
61         for (i = 0; i < 8; i++)
62             scanf("%d", arr + i);
63         for (i = zip(arr), j = 0; i != origin && j < n; j++) {
64             s[j] = record[i];
65             switch (s[j]) {
66                 case 'A':
67                     i = OP_A(i);
68                     break;
69                 case 'B':
70                     i = resume_B(i);
71                     break;
72                 case 'C':
73                     i = resume_C(i);
74                     break;
75             }
76         }
77         if (i != origin)
78             printf("-1
");
79         else {
80             printf("%d ", j);
81             while (j--)
82                 putchar(s[j]);
83             putchar('
');
84         }
85     }
86     return 0;
87 }

시간 0.01s, 공간 1120kb.
가장 좋은 0.00s에 대해 본인의 능력이 한계가 있어서 도저히 생각할 수 없습니다. 만약에 큰 신이 가르침을 주신다면 정례배를 하겠습니다.