这道题可以说是ida*的“模板"题
ida*就是迭代加深搜索+估价,枚举层数,开始dfs,到枚举的层数就停止,这样的好处是有bfs的顺序(速度),剩下了bfs的空间。
什么是估价呢,估价就是计算一个当前方案的价值,找一个比较理想的先搜索,这样理论上可以加速搜索的过程,一个好的估价函数可以让你的搜索直接找到正解(虽然不大可能)
这道题就是将上下左右的移动当成一种状态,每次搜索动哪一根,估价函数为中间的八个格子有几个相等的(原因是题目求最少几次可以让中间的变成一样的数),每次迭代加深就可以了。
这题有很多细节,比如说题目中的读入非常玄学,按照1~24的顺序从上往下,从左往右读,这就需要一些处理来计算出每一根上面的数存在哪里。其他细节详见代码注释。
#include<iostream>
using namespace std;
// 1 2
// 3 4
// 5 6 7 8 9 10 11
// 12 13
// 14 15 16 17 18 19 20
// 21 22
// 23 24 随手打下的草稿,用来对照题目中的输入,处理细节
int zhong[8]={7,8,9,12,13,16,17,18};//记录中心块读入的下标
int a[100];
int b[8][7]={{1,3,7,12,16,21,23},{2,4,9,13,18,22,24},{11,10,9,8,7,6,5},{20,19,18,17,16,15,14},
{24,22,18,13,9,4,2},{23,21,16,12,7,3,1},{14,15,16,17,18,19,20},{5,6,7,8,9,10,11}};//记录8种操作挪动的下标
int back[8]={5,4,7,6,1,0,3,2};
int count(int x){//数在8个中心块种有多少个x
int cnt=0;
for(int i=0;i<=7;i++)if(a[zhong[i]]==x)cnt++;
return cnt;
}
int calc(){//算出中心块中有多少个1,2,3,求出价值(估价部分)
return 8-max(max(count(1),count(2)),count(3));
}
void move(int n){//使用第n种操作移动,这里用到了之前处理的每一根上面的下标
int q=a[b[n][0]];
for(int i=1;i<=6;i++){//去掉最后一个,共6个
a[b[n][i-1]]=a[b[n][i]];
}
a[b[n][6]]=q;//注意细节,最后一个需要单独赋值
}
char c[100000];
void output(){//这个是调试用的输出函数,挺复杂的,挑不出来的同学们可以用他输出调试
cout<<" "<<a[1]<<" "<<a[2]<<endl;
cout<<" "<<a[3]<<" "<<a[4]<<endl;
cout<<a[5]<<" "<<a[6]<<" "<<a[7]<<" "<<a[8]<<" "<<a[9]<<" "<<a[10]<<" "<<a[11]<<endl;
cout<<" "<<a[12]<<" "<<a[13]<<endl;
cout<<a[14]<<" "<<a[15]<<" "<<a[16]<<" "<<a[17]<<" "<<a[18]<<" "<<a[19]<<" "<<a[20]<<endl;
cout<<" "<<a[21]<<" "<<a[22]<<endl;
cout<<" "<<a[23]<<" "<<a[24];
}
bool dfs(int now,int last,int limit){//搜索函数,返回值是搜没搜到解,如果搜到了解,答案就是迭代加深的层数
//output();
//cout<<endl<<"-------------------------------"<<endl;
if(calc()==0){//如果全部一样,就有解
return 1;
}
if(calc()+now>limit)return 0;//剪枝,如果最少步数还超过了层数限制,就没有解了
for(int i=0;i<=7;i++){//枚举是哪一种移动
// cout<<(char)(i+'A')<<endl;
//if(i==last)continue;
move(i);
c[now+1]=i+'A';//记录移动方案,准备输出
if(dfs(now+1,i,limit))return 1;//如果搜到了解,返回true
move(back[i]); //这里要回溯,很重要的细节,back[i]表示i的逆操作
}
return 0;
}
int main(){
//freopen("out.txt","w",stdout);
while(1){
cin>>a[1];
if(a[1]==0)return 0;
for(int i=2;i<=24;i++)cin>>a[i];
if(calc()==0)cout<<"No moves needed"<<endl<<a[zhong[1]]<<endl;//细节,如果不需要移动,直接输出
else{
int ans=1;
while(1){//迭代加深,枚举层数
if(dfs(0,-1,ans)){//如果在ans层内有解,答案为ans
break;
}
ans++;
}
for(int i=1;i<=ans;i++)cout<<c[i];//输出移动的方案
cout<<endl<<a[zhong[1]]<<endl;//输出中心块颜色
}
}
}