[原创]HDU 1430 魔板 [BFS+康拓展开]【数学】

2016-11-05 16:48:35 Tabris_ 阅读数：574

博客爬取于2020-06-14 22:42:50
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/53046282

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1430
---------------------------------------------.
魔板

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2968 Accepted Submission(s): 672

Problem Description
在魔方风靡全球之后不久，Rubik先生发明了它的简化版——魔板。魔板由8个同样大小的方块组成，每个方块颜色均不相同，可用数字1-8分别表示。任一时刻魔板的状态可用方块的颜色序列表示：从魔板的左上角开始，按顺时针方向依次写下各方块的颜色代号，所得到的数字序列即可表示此时魔板的状态。例如，序列(1,2,3,4,5,6,7,8)表示魔板状态为：

1 2 3 4
8 7 6 5

对于魔板，可施加三种不同的操作，具体操作方法如下：

A: 上下两行互换,如上图可变换为状态87654321
B: 每行同时循环右移一格,如上图可变换为41236785
C: 中间4个方块顺时针旋转一格,如上图可变换为17245368

给你魔板的初始状态与目标状态，请给出由初态到目态变换数最少的变换步骤，若有多种变换方案则取字典序最小的那种。

Input
每组测试数据包括两行，分别代表魔板的初态与目态。

Output
对每组测试数据输出满足题意的变换步骤。

Sample Input
12345678
17245368
12345678
82754631

Sample Output
C
AC

Author
LL

---------------------------------------------.

题目大意 ：中文题 自己读。。。。

解题思路：

首先可以明确的是 这个字符串改变之前和改变之后的关系是一定有的 那么原串和终串无论是什么 只要讲原串和终串映射回“12345678”这样的话 就能够计算了

那样的话 所有的解都可以变成 “12345678” 这个串的变化 ；
由于 8！=40320 状态数目非常少 变化也只有三种 那么我们只要用BFS就可以了 利用广度优先的特性 求出的解也是最优的

那么首先BFS预处理结果一下就行了 串的变化模拟就可以了
后来计算的时候 把原串和终串处理一下 变成"12345678"与"balabala"的样子 然后输出结果就行了

但是在标记的时候 想到用康托展开的值来标记 而不是用map映射（但是想想map映射 也没什么毛病吧）。

这个代码确实是AC的 只是win7 CB13.2 运行会渣掉 找了1天BUG还是没有找到 最后提交上去想保存一下代码的时候 发现居然AC了!! AC了!

附本题代码
----------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
# include <bits/stdc++.h>
using namespace std;

# define INF      0x3f3f3f3f
# define pb       push_back
# define abs(a)   ((a)>0?(a):-(a))
# define min(a,b) ((a)>(b)?(a):(b))
# define lalal    puts("*******")

typedef long long int LL ;
typedef unsigned long long int LLu ;
/*******************************/

bool vis[40050];
int  jiecheng[10]={1,1,2,6,24,120,720,5040,40320,362880};

int Cantor_expansion(string &a){
    int x=0,tem=0;
    for(int i=0;i<8;i++){
        tem = 0;
        for(int j=i+1;j<8;j++)
            if(a[j]<a[i]) tem++;
        x+=tem*jiecheng[7-i];
    }
    return x;
}

void op_A(string &a){
    for(int i=0;i<4;i++) swap(a[i],a[7-i]);
}

void op_B(string &a){
    char t=a[0];
    for(int i=1;i<4;i++) swap(t,a[i]);
    a[0]=t;
    t=a[7];
    for(int i=7;i>=4;i--) swap(t,a[i]);
    a[7]=t;
}

void op_C(string &a){
    swap(a[1],a[2]);
    swap(a[1],a[5]);
    swap(a[1],a[6]);
}

struct node {
    string str,step;
    int x;
};

string mmp[44444];

void BFS(){
    memset(vis,false,sizeof(vis));
    queue<node >q;
    string a="12345678";
    int x=Cantor_expansion(a);
    vis[x]=1;
    mmp[x]="";
    node tem ,tmp;
    tem.str=a;
    tem.step="";
    tem.x=x;
    q.push(tem);

    while(!q.empty()){
        tmp=q.front();q.pop();
        //AAAAAAAAAAAAA
        tem=tmp;
        op_A(tem.str);
        tem.x=Cantor_expansion(tem.str);
        if(!vis[tem.x]){
            vis[tem.x]=true;
            tem.step+="A";
            mmp[tem.x]=tem.step;
            q.push(tem);
        }
        //BBBBBBBBBBBBB
        tem=tmp;
        op_B(tem.str);
        tem.x=Cantor_expansion(tem.str);
        if(!vis[tem.x]){
            vis[tem.x]=true;
            tem.step+="B";
            mmp[tem.x]=tem.step;
            q.push(tem);
        }
        //CCCCCCCCCCCCC
        tem=tmp;
        op_C(tem.str);
        tem.x=Cantor_expansion(tem.str);
        if(!vis[tem.x]){
            vis[tem.x]=true;
            tem.step+="C";
            mmp[tem.x]=tem.step;
            q.push(tem);
        }
    }
    return ;
}

void change(string &a,string &b){
    map<char,char>mp;
    for(int i=0;i<a.size();i++)
        mp[a[i]]='1'+i;

    for(int i=0;i<b.size();i++)
        b[i]=mp[b[i]];

    return ;
}

int main(){

    BFS();

    string a1,b1;
    while(cin>>a1>>b1){
        change(a1,b1);
        int x=Cantor_expansion(b1);
        cout<<mmp[x]<<endl;
    }
    return 0;
}

----------------------------.