Problem Description

在小白成功的通过了第一轮面试后，他来到了第二轮面试。面试的题目有点难度了，为了考核你的思维能量，面试官给你一副（2x4）的初态地图，然后在给你一副（2x4）的终态地图。每一幅地图都是有数字1~8表示，给你的地图的信息是一串序列，然后根据这序列，从地图的左上角开始，按照顺时针排列。比如地图信息为12345678，则表示地图：

1 2 3 4

8 7 6 5

对于这地图有三种具体操作方式：

A: 上下两行互换,如上图可变换为状态87654321

B: 每行同时循环右移一格,如上图可变换为41236785

C: 中间4个方块顺时针旋转一格,如上图可变换为17245368

根据所给的初状地图和终态地图，请给出完成转化的最少的变换步骤，若有多种变换方案则取字典序最小的那种。

Input

每组测试数据包括两行，分别代表地图信息的初态与终态。

Output

对于每次测试案例，输出需要符合要求的变换步骤。

SampleInput

SampleOutput

C

AC

最开始预处理了一下直接搜，本地爆炸。
然后想到了用康托展开打个表，然后。。。就AC了。
这里讲一下康托展开算法
　　X = An * (n-1)! + A_n-1 * (n-2)! + ... + A₁ * 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位。

代码实现的话就是：

 int fac[] = {,,,,,,,,};  //i的阶乘

 int kangtuo(int n,char a[]){  //n表示1~n个数，a数组表示数字

     int i,j,t,res = ;

     for(i = ; i < n; i++){

         t = ;

         for(j = i+; j < n; j++)

             if(a[i] > a[j])

                 t++;

         res += t*fac[n-i-];

     }

     return sum + ;

 }

知道了康托展开后，就可以打表做了，值得一提的是这道题的预处理。因为题目输入两组字符串分别表示初始状态和结束状态，而我们打表是从12345678到各个状态的值，所以预处理我们把输入的初状态转成12345678，末状态也执行相应转换就可以了；

代码：

 #include <iostream>

 #include <string>

 #include <cstdio>

 #include <cstdlib>

 #include <sstream>

 #include <iomanip>

 #include <map>

 #include <stack>

 #include <deque>

 #include <queue>

 #include <vector>

 #include <set>

 #include <list>

 #include <cstring>

 #include <cctype>

 #include <algorithm>

 #include <iterator>

 #include <cmath>

 #include <bitset>

 #include <ctime>

 #include <fstream>

 #include <limits.h>

 #include <numeric>

 using namespace std;

 #define F first

 #define S second

 #define mian main

 #define ture true

 #define MAXN 1000000+5

 #define MOD 1000000007

 #define PI (acos(-1.0))

 #define EPS 1e-6

 #define MMT(s) memset(s, 0, sizeof s)

 typedef unsigned long long ull;

 typedef long long ll;

 typedef double db;

 typedef long double ldb;

 typedef stringstream sstm;

 const int INF = 0x3f3f3f3f;

 struct node{

     string str,step;

 };

 bool vis[+];

 int  pos[],fac[] = {,,,,,,,,};

 string ans[];

 int fun(string a){

     int i,j,t,sum = ;

     for(i = ; i < ; ++i){

         t = ;

         for(j = i+; j < ; ++j)

             if(a[i] > a[j])

                 ++t;

         sum += t*fac[-i-];

     }

     return sum+;

 }

 void ma(string &s){

     for(int i = ; i < ; ++i)

         swap(s[i],s[i+]);

 }

 string mb(string s){

     string temp = s;

     for(int i = ; i < ; ++i){

         if(i== || i==)

             temp[i]=s[i+];

         else

             temp[i]=s[i-];

     }

     return temp;

 }

 void mc(string &s){

     swap(s[],s[]);

     swap(s[],s[]);

     swap(s[],s[]);

 }

 void bfs( string s ){

     MMT(vis);

     queue<node>q;

     node pre,nxt;

     pre.str = s;

     pre.step = "";

     vis[fun(s)] = ;

     ans[fun(s)] = pre.step;

     q.push(pre);

     while(!q.empty()){

         pre = q.front();

         q.pop();

         nxt = pre;

         ma(nxt.str);

         if(!vis[fun(nxt.str)]){

             nxt.step += "A";

             vis[fun(nxt.str)] = ;

             ans[fun(nxt.str)] = nxt.step;

             q.push(nxt);

         }

         nxt.str = mb(pre.str);

         if(!vis[fun(nxt.str)]){

             nxt.step = pre.step + "B";

             vis[fun(nxt.str)] = ;

             ans[fun(nxt.str)] = nxt.step;

             q.push(nxt);

         }

         nxt = pre;

         mc(nxt.str);

         if(!vis[fun(nxt.str)]){

             nxt.step += "C";

             vis[fun(nxt.str)] = ;

             ans[fun(nxt.str)] = nxt.step;

             q.push(nxt);

         }

     }

 }

 int main(){

     ios_base::sync_with_stdio(false);

     cout.tie();

     cin.tie();

     string s1,s2;

     int k;

     bfs("");

     //12345678

     //17245368

     //12345678

     //

     while(cin>>s1>>s2){

         swap(s1[],s1[]);

         swap(s1[],s1[]);

         swap(s2[],s2[]);

         swap(s2[],s2[]);

         for(int i = ; i < ; i++)

             pos[s1[i]-''] = i+;

         for(int i = ; i < ; i++)

             s2[i] = pos[s2[i]-''];

         k = fun(s2);

         cout<<ans[k]<<endl;

     }

     return ;

 }

其实康托展开也可以求逆运算，具体思想以及代码实现这里就不讲了=7=

巴特西

转换地图（康托展开+预处理+BFS）

Problem Description

Input

Output

SampleInput

SampleOutput

最新文章

热门文章

巴特西

转换地图 （康托展开+预处理+BFS）

Problem Description

Input

Output

SampleInput

SampleOutput

最新文章

热门文章

转换地图（康托展开+预处理+BFS）