前言

这道题挺有趣的...嗯...有趣到我做了足足两节课...！

唉，应该还是因为自己太弱了

题目

题目背景

在成功地发明了魔方之后，鲁比克先生发明了它的二维版本，称作魔板。这是一张有8个大小相同的格子的魔板：

1 2 3 4

8 7 6 5

题目描述

我们知道魔板的每一个方格都有一种颜色。这8种颜色用前8个正整数来表示。可以用颜色的序列来表示一种魔板状态，规定从魔板的左上角开始，沿顺时针方向依次取出整数，构成一个颜色序列。对于上图的魔板状态，我们用序列（1，2，3，4，5，6，7，8）来表示。这是基本状态。

这里提供三种基本操作，分别用大写字母“A”，“B”，“C”来表示（可以通过这些操作改变魔板的状态）：

“A”：交换上下两行；

“B”：将最右边的一列插入最左边；

“C”：魔板中央四格作顺时针旋转。

下面是对基本状态进行操作的示范：

A:

8 7 6 5

1 2 3 4

B:

4 1 2 3

5 8 7 6

C:

1 7 2 4

8 6 3 5

对于每种可能的状态，这三种基本操作都可以使用。

你要编程计算用最少的基本操作完成基本状态到目标状态的转换，输出基本操作序列。

输入格式

只有一行，包括8个整数，用空格分开（这些整数在范围 1——8 之间）不换行，表示目标状态。

输出格式

Line 1: 包括一个整数，表示最短操作序列的长度。

Line 2: 在字典序中最早出现的操作序列，用字符串表示，除最后一行外，每行输出60个字符。

输入输出样例

输入 

2 6 8 4 5 7 3 1

输出 

7 BCABCCB

说明/提示

题目翻译来自NOCOW。

USACO Training Section 3.2

分析

（直接看正解请见第二根横线以下）

最开始看完题目感觉和曾经老师讲过的一道题很像（仅个人“臆想”！qwq！）：

【HDU1667 旋转游戏 The Rotation Game】

´如图所示形状的棋盘上分别有8个1、 2、 3，要按A~H方向旋转棋盘，每个方面的旋转操作是使某行或某列的数字循环移位。

´目标是使中间8个方格数字相同。

´例如，图7（a）进行A操作后变为图（b），再进行C操作后变为图（c），这正是一个目标状态（因为中间8个方格数字相同）。

要求旋转次数最少。 如果有多解，操作序列的字典序应尽量小。

分析：

´本题是一个典型的状态空间搜索问题，可惜如果直接套用八数码问题的框架会超时。 利用组合数学知识，这是一个多重集的全排列：8个1、 8个2、 8个3的全排列个数为24!/(8!*8!*8!)=9465511770。最坏情况下最多要处理这么多结点！

´解决方法很巧妙：本题要求的是中间8个数字相同，即8个1或者8个2或者8个3。 因此可以分3次求解。 当目标是“中间8个数字都是1”时，2和3就没有区别了（都是“非1”），因此状态总数变成了8个1，16个“非1”的全排列个数，即24!/(8!*16!)=735471，在可以接受的范围内了，总的时间还要再乘以3。

总结一下，大约做法就是【IDA*】启发函数、估值函数之类的

---

这里只是提一下...接下来步入正题

在想到IDA*后，感觉可以做，但由于“自己太弱”+“3.2要求应该没那么高”

就想打普通的暴搜——DFS

打完后发现了一个问题：DFS是“一搜到底”，对本题显然不合适，会超时

而BFS是一层一层地搜索，能满足答案长度最小，于是转而打BFS

---

这道题有个重点：它的输入输出顺序是这样的：

于是做变换时要格外注意，不要出错（调了好久...）

总体思路很简单：

1.记录并搜索答案（关于“A”“B”“C”的字符串）

2.检查该答案是否合法

3.合法就输出，程序结束

4.不合法就扩展答案，继续搜

奇妙的DFS代码

打这个代码时，读错题了，还没改过来，我误以为是求“给出的字符串变成基础字符串的方案”

/* ID:lunasmi2 TASK:msquare LANG:C++ */ #include<cstdio> #include<cmath> #include<map> #include<string> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int MAXN=1e6; int tmp[10]; map<string,bool> vis; string a,b="x12348765",ans; void Change1() { for(int i=1;i<=4;i++) swap(a[i],a[i+4]); } void Restore1() { for(int i=1;i<=4;i++) swap(a[i],a[i+4]); } void Change2() { for(int i=1;i<=3;i++) { swap(a[i],a[i+1]); swap(a[i+4],a[i+4+1]); } } void Restore2() { for(int i=4;i>=2;i--) { swap(a[i],a[i-1]); swap(a[i+4],a[i+4-1]); } } void Change3() { char tmp=a[2]; a[2]=a[6],a[6]=a[7],a[7]=a[3],a[3]=tmp; } void Restore3() { char tmp=a[2]; a[2]=a[3],a[3]=a[7],a[7]=a[6],a[6]=tmp; } void dfs(int id,int x) { if(x==1) ans+='A'; if(x==2) ans+='B'; if(x==3) ans+='C'; if(vis[a]) return ; vis[a]=1; cout<<ans<<endl; if(a==b) { printf("%d\n",id); cout<<ans<<endl; exit(0); } Change1();dfs(id+1,1);Restore1();ans.erase(ans.end()-1); Change2();dfs(id+1,2);Restore2();ans.erase(ans.end()-1); Change3();dfs(id+1,3);Restore3();ans.erase(ans.end()-1); } int main() { //freopen("msquare.in","r",stdin); //freopen("msquare.out","w",stdout); a+='x';//0位随便补上qwq...习惯从1开始 for(int i=1;i<=8;i++) { scanf("%d",&tmp[i]); if(1<=i&&i<=4) a+=tmp[i]+'0'; } for(int i=8;i>=5;i--) a+=tmp[i]+'0'; cout<<a<<endl; dfs(0,0); return 0; }

BFS代码

/* ID:lunasmi2 TASK:msquare LANG:C++ */ #include<cstdio> #include<cmath> #include<map> #include<queue> #include<string> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int MAXN=1e6; int tmp[10]; map<string,bool> vis; string a="x12345678",b; struct node { string ans,a; }; void Change1(string &a) { for(int i=1;i<=4;i++) swap(a[i],a[8-i+1]); } void Restore1(string &a) { for(int i=1;i<=4;i++) swap(a[i],a[8-i+1]); } void Change2(string &a) { for(int i=1;i<=3;i++) { swap(a[4-i+1],a[4-i]); swap(a[i+4],a[i+4+1]); } } void Restore2(string &a) { for(int i=1;i<=3;i++) { swap(a[i],a[i+1]); swap(a[8-i+1],a[8-i]); } } void Change3(string &a) { char tmp=a[2]; a[2]=a[7],a[7]=a[6],a[6]=a[3],a[3]=tmp; } void Restore3(string &a) { char tmp=a[2]; a[2]=a[3],a[3]=a[6],a[6]=a[7],a[7]=tmp; } void BFS() { if(a==b) { printf("0\n\n"); exit(0); } queue<node> que; node q; q.a=a; que.push(q); while(1) { q=que.front();que.pop(); if(q.a==b) { cout<<q.ans.size()<<endl<<q.ans<<endl; exit(0); } if(vis[q.a]) continue; vis[q.a]=1; Change1(q.a);q.ans+='A';que.push(q);Restore1(q.a);q.ans.erase(q.ans.end()-1); Change2(q.a);q.ans+='B';que.push(q);Restore2(q.a);q.ans.erase(q.ans.end()-1); Change3(q.a);q.ans+='C';que.push(q);Restore3(q.a);q.ans.erase(q.ans.end()-1); } } int main() { //freopen("msquare.in","r",stdin); //freopen("msquare.out","w",stdout); b+='x';//0位随便补上qwq...习惯从1开始 for(int i=1;i<=8;i++) { scanf("%d",&tmp[i]); b+=tmp[i]+'0'; } BFS(); return 0; }

总结

通过这道题又熟悉了一下Map和String的用法，并且从审题到码代码到AC，经历了十分有趣的思路变化

所以感觉有必要写个博客qwq...记录一下

新收获：【去除String字符串最末尾字符的方法】

s.end( )指向的是字符串末尾+1的位置

s.erase(s.end()-1);