HDU_1430 魔板【BFS+康托展开+置换】

一、题面

POJ1430

二、分析

该题与之前做的八数码不同，它是一个2*4的棋盘，并且没有空的区域。这样考虑的情况是很少的，依然结合康托展开，这时康托展开最多也只乘7的阶乘，完全可以BFS先预处理一遍。

这里需要注意，在处理的时候，仔细读题，他的二维变一维的顺序是顺时针一遍读过来的。

预处理完后，这里需要用一个小技巧，就是置换。

$$ \begin{pmatrix} 3 & 2 & 1 & 4 & 5 & 6 & 7 & 8\\1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \end{pmatrix} $$

上面使用的例子是$32145678$，然后相当于把它移到了和$12345678$一个起跑线上，这样做的好处就是我们预处理的答案能够适用所有情况。

假设目标状态是$87654321$，这样把目标状态置换成与上面对应的即可。

$$ \begin{pmatrix} 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1\\8 & 7 & 6 & 5 & 4 & 1 & 2 & 3 \\ \end{pmatrix} $$

这样就可以直接输出结果了。

三、AC代码

 #include <cstdio>

 #include <iostream>

 #include <fstream>

 #include <cstring>

 #include <queue>

 #include <algorithm>

 using namespace std;

 const int MAXN = ;

 const int fac[] = {, , , , , , , , , };    //factorial

 bool visit[MAXN];

 struct Node

 {

     int m[];

     int cat;

 };

 char op[] = "ABC";

 string ans[MAXN];

 void A(Node &t)

 {

     std::reverse(t.m , t.m+);

 }

 void B(Node &t)

 {

     int temp = t.m[];

     for(int i = ; i > ; i--)

     {

         t.m[i] = t.m[i-];

     }

     t.m[] = temp;

     temp = t.m[];

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

     {

         t.m[i] = t.m[i+];

     }

     t.m[] = temp;

 }

 void C(Node &t)

 {

     int temp = t.m[];

     t.m[] = t.m[];

     t.m[] = t.m[];

     t.m[] = t.m[];

     t.m[] = temp;

 }

 int Cantor(int s[])

 {

     int t, ans = ;

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

     {

         t = ;

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

         {

             if(s[j] < s[i])

                 t++;

         }

         ans += t*fac[-i];

     }

     return ans;

 }

 void bfs()

 {

     memset(visit, , sizeof(visit));

     Node t;

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

         t.m[i] = i+;

     t.cat = Cantor(t.m);

     queue<Node> Q;

     ans[t.cat] = "";

     visit[t.cat] = ;

     Q.push(t);

     while(!Q.empty())

     {

         Node p = Q.front();

         Q.pop();

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

         {

             t = p;

             switch(i)

             {

                 case : A(t);break;

                 case : B(t);break;

                 case : C(t);break;

             }

             t.cat = Cantor(t.m);

             if( !visit[t.cat] )

             {

                 ans[t.cat] = ans[p.cat]+op[i];

                 visit[t.cat] = ;

                 Q.push(t);

             }

         }

     }

 }

 int main()

 {

     //freopen("input.txt", "r", stdin);

     //freopen("out.txt", "w", stdout);

     char s[];

     int a[] = {}, b[] = {};

     bfs();

     while(scanf("%s", s)!=EOF)

     {

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

         {

             a[s[i] - ''] = i+;

         }

         scanf("%s", s);

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

         {

             b[i] = a[s[i] - ''];

         }

         cout << ans[Cantor(b)] << endl;

     }

     return ;

 }

巴特西

HDU_1430 魔板【BFS+康托展开+置换】

一、题面

二、分析

三、AC代码

最新文章

热门文章

巴特西

HDU_1430 魔板 【BFS+康托展开+置换】

一、题面

二、分析

三、AC代码

最新文章

热门文章

HDU_1430 魔板【BFS+康托展开+置换】