【题目背景】
在成功地发明了魔方之后,鲁比克先生发明了它的二维版本,称作魔板。这是一张有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
【分析】
众所周知,这是一道广搜题,那么本题的大体思路就明确了,剩下的就是耐心地解决一些细节问题。
-
降维打击
魔板原本是2×4的矩阵,但一维处理起来一定比二维方便,于是便可以降维,但,要注意技巧。
以样例来说,括号里面代表这个数储存的一维数组的位置
2(a1) | 6(a2) | 8(a3) | 4(a4) |
5(a5) | 7(a6) | 3(a7) | 1(a8) |
具体实现请看代码:
for(int i=1;i<=8;i++){//基本状态 if(i<=4) sak[1].before[i]=i; if(i>4) sak[1].before[i]=13-i; }
for(int i=1;i<=4;i++)//双循环输入目标状态(真~~朴素~~) scanf("%d",&after[i]); for(int i=8;i>=5;i--) scanf("%d",&after[i]);
-
判重问题
8个数排列组合一定,所以只需要判定前七个数就一定能知道最后一个数,这样就不会超出内存限制啦。然后用标记数组给这个七位数打个标记。
int pan(int a[]){//自定义pan函数用来判重 int ans=0; for(int i=7;i>=1;i--) ans=ans*10+a[i]; return ans; }
三种操作
无脑模拟。
合理使用结构体使代码不复杂
尽量保证广搜框架完整
其他细节问题
ac代码
#include <bits/stdc++.h> using namespace std; int after[9],ans,o,jishu;//after数组为目标状态,o和jishu为累加器辅助判断一些奇怪的东西 bool fla[9000005],k; struct sakura{//结构体 int before[9],f;char step; }sak[100086]; int pan(int a[]){//自定义pan函数用来判重 int ans=0; for(int i=7;i>=1;i--) ans=ans*10+a[i]; return ans; } bool judge(int a[]){ for(int i=1;i<=8;i++) if(a[i]!=after[i]) return 0; return 1; } void print(int a){//递归输出 if(sak[a].f!=0){ o++; print(sak[a].f); } if(!sak[a].f) return; if(!k){//输出步数 printf("%dn",o); k=1; } printf("%c",sak[a].step); jishu++; if(!jishu%60)//隔60个换行 printf("n"); } void bfs(){ int h=0,t=1;sak[t].f=0; while(h<t){ h++; for(int i=1;i<=3;i++){//保证框架完整 int bit[9]; if(i==1){//a操作 for(int i=1;i<=4;i++){ bit[i]=sak[h].before[i+4]; bit[i+4]=sak[h].before[i]; } } if(i==2){//b操作 bit[1]=sak[h].before[4];bit[5]=sak[h].before[8]; bit[2]=sak[h].before[1];bit[6]=sak[h].before[5]; bit[3]=sak[h].before[2];bit[7]=sak[h].before[6]; bit[4]=sak[h].before[3];bit[8]=sak[h].before[7]; } if(i==3){//c操作 bit[1]=sak[h].before[1]; bit[2]=sak[h].before[6]; bit[3]=sak[h].before[2]; bit[4]=sak[h].before[4]; bit[5]=sak[h].before[5]; bit[8]=sak[h].before[8]; bit[7]=sak[h].before[3]; bit[6]=sak[h].before[7]; } if(!fla[pan(bit)]){ t++; if(i==1) sak[t].step='a'; if(i==2) sak[t].step='b'; if(i==3) sak[t].step='c'; fla[pan(bit)]=1;//标记 sak[t].f=h;//记录爸爸 for(int i=1;i<=8;i++) sak[t].before[i]=bit[i]; if(ans==pan(bit)){ print(t); exit(0);//万恶之源结束 } } } } } int main(){ for(int i=1;i<=8;i++){//降维打击 if(i<=4) sak[1].before[i]=i; if(i>4) sak[1].before[i]=13-i; } fla[pan(sak[1].before)]=1; for(int i=1;i<=4;i++) scanf("%d",&after[i]); for(int i=8;i>=5;i--) scanf("%d",&after[i]); ans=pan(after); if(ans==pan(sak[1].before)){//特判(貌似并不需要) printf("0n"); return 0; } bfs();//万恶之源开始 return 0; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/605423.html