Problem Description
在小白成功的通过了第一轮面试后，他来到了第二轮面试。面试的题目有点难度了，为了考核你的思维能量，面试官给你一副（2x4）的初态地图，然后在给你一副（2x4）的终态地图。每一幅地图都是有数字1~8表示，给你的地图的信息是一串序列，然后根据这序列，从地图的左上角开始，按照顺时针排列。 比如地图信息为12345678，则表示地图：
1 2 3 4
8 7 6 5
对于这地图有三种具体操作方式：
A: 上下两行互换,如上图可变换为状态87654321
B: 每行同时循环右移一格,如上图可变换为41236785
C: 中间4个方块顺时针旋转一格,如上图可变换为17245368
根据所给的初状地图和终态地图，请给出完成转化的最少的变换步骤，若有多种变换方案则取字典序最小的那种。
1 2 3 4
8 7 6 5
对于这地图有三种具体操作方式：
A: 上下两行互换,如上图可变换为状态87654321
B: 每行同时循环右移一格,如上图可变换为41236785
C: 中间4个方块顺时针旋转一格,如上图可变换为17245368
根据所给的初状地图和终态地图，请给出完成转化的最少的变换步骤，若有多种变换方案则取字典序最小的那种。
Input
每组测试数据包括两行，分别代表地图信息的初态与终态。
Output
对于每次测试案例，输出需要符合要求的变换步骤。
SampleInput
12345678 17245368 12345678 82754631
SampleOutput
C AC
最开始预处理了一下直接搜，本地爆炸。
然后想到了用康托展开打个表，然后。。。就AC了。
这里讲一下康托展开算法
X = An * (n-1)! + An-1 * (n-2)! + ... + A1 * 0!;
康拓展开就是求一个数字字符串在其全排列中的位置。
例如231这个数，全排列为123 132 213 231 312 321
所以231排在第4位，那么康托展开算法是如何求的呢。
例如求231的康托展开，从头至尾依次判断：
- 第一位数2，比2小的有一个，有1*2！
- 第二位数3，比3小的有两个，但2已经出现，有1*1！
- 第三位数1，有0*0！
累加起来就是2 + 1 = 3，表示比231小的有3个，所以231排在第4位。
代码实现的话就是：
1 int fac[] = {1,1,2,6,24,120,720,5040,40320}; //i的阶乘 2 int kangtuo(int n,char a[]){ //n表示1~n个数，a数组表示数字 3 int i,j,t,res = 0; 4 for(i = 0; i < n; i++){ 5 t = 0; 6 for(j = i+1; j < n; j++) 7 if(a[i] > a[j]) 8 t++; 9 res += t*fac[n-i-1]; 10 } 11 return sum + 1; 12 }
知道了康托展开后，就可以打表做了，值得一提的是这道题的预处理。因为题目输入两组字符串分别表示初始状态和结束状态，而我们打表是从12345678到各个状态的值，所以预处理我们把输入的初状态转成12345678，末状态也执行相应转换就可以了；
代码：
1 #include <iostream> 2 #include <string> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <sstream> 6 #include <iomanip> 7 #include <map> 8 #include <stack> 9 #include <deque> 10 #include <queue> 11 #include <vector> 12 #include <set> 13 #include <list> 14 #include <cstring> 15 #include <cctype> 16 #include <algorithm> 17 #include <iterator> 18 #include <cmath> 19 #include <bitset> 20 #include <ctime> 21 #include <fstream> 22 #include <limits.h> 23 #include <numeric> 24 25 using namespace std; 26 27 #define F first 28 #define S second 29 #define mian main 30 #define ture true 31 32 #define MAXN 1000000+5 33 #define MOD 1000000007 34 #define PI (acos(-1.0)) 35 #define EPS 1e-6 36 #define MMT(s) memset(s, 0, sizeof s) 37 typedef unsigned long long ull; 38 typedef long long ll; 39 typedef double db; 40 typedef long double ldb; 41 typedef stringstream sstm; 42 const int INF = 0x3f3f3f3f; 43 44 struct node{ 45 string str,step; 46 }; 47 48 bool vis[40320+1]; 49 int pos[10],fac[] = {1,1,2,6,24,120,720,5040,40320}; 50 string ans[41000]; 51 52 53 int fun(string a){ 54 int i,j,t,sum = 0; 55 for(i = 0; i < 8; ++i){ 56 t = 0; 57 for(j = i+1; j < 8; ++j) 58 if(a[i] > a[j]) 59 ++t; 60 sum += t*fac[8-i-1]; 61 } 62 return sum+1; 63 } 64 65 void ma(string &s){ 66 for(int i = 0; i < 4; ++i) 67 swap(s[i],s[i+4]); 68 } 69 70 string mb(string s){ 71 string temp = s; 72 for(int i = 0; i < 8; ++i){ 73 if(i==0 || i==4) 74 temp[i]=s[i+3]; 75 else 76 temp[i]=s[i-1]; 77 } 78 return temp; 79 } 80 81 void mc(string &s){ 82 swap(s[1],s[2]); 83 swap(s[5],s[6]); 84 swap(s[1],s[6]); 85 } 86 87 void bfs( string s ){ 88 MMT(vis); 89 queue<node>q; 90 node pre,nxt; 91 92 pre.str = s; 93 pre.step = ""; 94 vis[fun(s)] = 1; 95 ans[fun(s)] = pre.step; 96 q.push(pre); 97 98 while(!q.empty()){ 99 pre = q.front(); 100 q.pop(); 101 102 nxt = pre; 103 ma(nxt.str); 104 if(!vis[fun(nxt.str)]){ 105 nxt.step += "A"; 106 vis[fun(nxt.str)] = 1; 107 ans[fun(nxt.str)] = nxt.step; 108 q.push(nxt); 109 } 110 111 nxt.str = mb(pre.str); 112 if(!vis[fun(nxt.str)]){ 113 nxt.step = pre.step + "B"; 114 vis[fun(nxt.str)] = 1; 115 ans[fun(nxt.str)] = nxt.step; 116 q.push(nxt); 117 } 118 119 nxt = pre; 120 mc(nxt.str); 121 if(!vis[fun(nxt.str)]){ 122 nxt.step += "C"; 123 vis[fun(nxt.str)] = 1; 124 ans[fun(nxt.str)] = nxt.step; 125 q.push(nxt); 126 } 127 } 128 } 129 130 int main(){ 131 ios_base::sync_with_stdio(false); 132 cout.tie(0); 133 cin.tie(0); 134 string s1,s2; 135 int k; 136 bfs("12345678"); 137 //12345678 138 //17245368 139 //12345678 140 //82754631 141 while(cin>>s1>>s2){ 142 swap(s1[4],s1[7]); 143 swap(s1[5],s1[6]); 144 swap(s2[4],s2[7]); 145 swap(s2[5],s2[6]); 146 for(int i = 0; i < 8; i++) 147 pos[s1[i]-'0'] = i+1; 148 for(int i = 0; i < 8; i++) 149 s2[i] = pos[s2[i]-'0']; 150 k = fun(s2); 151 cout<<ans[k]<<endl; 152 } 153 return 0; 154 }
其实康托展开也可以求逆运算，具体思想以及代码实现这里就不讲了=7=
