第30题 #include <iostream>  #include <queue>  using namespace std;      const int maxl = 2

1. #include <iostream> 
2. #include <queue> 
3. using namespace std; 
4.    
5. const int maxl = 2000000000; 
6.    
7. class Map { 
8.     struct item { 
9.         string key; int value; 
10.     } d[maxl]; 
11.     int cnt; 
12. public: 
13.     int find(string x) { 
14.         for (int i = 0; i < cnt; i++) 
15.             if (d[i].key == x) 
16.                 return d[i].value; 
17.         return -1; 
18.     } 
19.     static int end() { return -1; } 
20.     void insert(string k, int v) { 
21.         d[cnt].key = k; d[cnt++].value = v; 
22.     } 
23. } s[2]; 
24.    
25. class Queue { 
26.     string q[maxl]; 
27.     int head, tail; 
28. public: 
29.     void pop() { ++head; } 
30.     string front() { return q[head + 1]; } 
31.     bool empty() { return head == tail; } 
32.     void push(string x) { q[++tail] = x; } 
33. } q[2]; 
34.    
35. string st0, st1; 
36. int m; 
37.    
38. string LtoR(string s, int L, int R) { 
39.     string t = s; 
40.     char tmp = t[L]; 
41.     for (int i = L; i < R; ++i) 
42.         t[i] = t[i + 1]; 
43.     t[R] = tmp; 
44.     return t; 
45. } 
46.    
47. string RtoL(string s, int L, int R) { 
48.     string t = s; 
49.     char tmp = t[R]; 
50.     for (int i = R; i > L; --i) 
51.         t[i] = t[i - 1]; 
52.     t[L] = tmp; 
53.     return t; 
54. } 
55.    
56. bool check(string st, int p, int step) { 
57.     if (s[p].find(st) != s[p].end()) 
58.         return false; 
59.     ++step; 
60.     if (s[p ^ 1].find(st) == s[p].end()) { 
61.         s[p].insert(st, step); 
62.         q[p].push(st); 
63.         return false; 
64.     } 
65.     cout << s[p ^ 1].find(st) + step << endl; 
66.     return true; 
67. } 
68.    
69. int main() { 
70.     cin >> st0 >> st1; 
71.     int len = st0.length(); 
72.     if (len != st1.length()) { 
73.         cout << -1 << endl; 
74.         return 0; 
75.     } 
76.     if (st0 == st1) { 
77.         cout << 0 << endl; 
78.         return 0; 
79.     } 
80.     cin >> m; 
81.     s[0].insert(st0, 0); s[1].insert(st1, 0); 
82.     q[0].push(st0); q[1].push(st1); 
83.     for (int p = 0; 
84.          !(q[0].empty() && q[1].empty()); 
85.          p ^= 1) { 
86.         string st = q[p].front(); q[p].pop(); 
87.         int step = s[p].find(st); 
88.         if ((p == 0 && 
89.               (check(LtoR(st, m, len - 1), p, step) || 
90.                check(RtoL(st, 0, m), p, step))) 
91.                   || 
92.             (p == 1 && 
93.               (check(LtoR(st, 0, m), p, step) || 
94.                check(RtoL(st, m, len - 1), p, step)))) 
95.             return 0; 
96.     } 
97.     cout << -1 << endl; 
98.     return 0; 
99. } 

3）判断：若两个字符串的长度均为 n，则最坏情况下，此程序的时间复杂度为 Θ(n!)。（ ）wKC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库