题意:

  给出图,往A-H方向旋转,使中间8个格子数字相同。要求旋转次数最少,操作序列字典序尽量小。

分析:

  用一维数组存24个方格。二维数组代表每个方向对应的7个方格。IDA*剪枝是当8-8个方格中重复字母最多的那个字母数量>maxd。

代码:

  

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
int a[24];
int d[8][7]=
{
{0,2,6,11,15,20,22},
{1,3,8,12,17,21,23},
{10,9,8,7,6,5,4},
{19,18,17,16,15,14,13},
{23,21,17,12,8,3,1},
{22,20,15,11,6,2,0},
{13,14,15,16,17,18,19},
{4,5,6,7,8,9,10},
};
int g[8]={6,7,8,11,12,15,16,17};
int ans;
string p;
bool dfs(int now,int maxd,string path)
{
//cout<<1<<endl;
if(now==maxd)
{
//cout<<maxd<<endl;
int ok=1;
for(int i=1;i<8;i++)
{
if(a[g[i]]!=a[g[i-1]])
{
ok=0;
break;
}
}
if(!ok)
return false;
ans=a[g[0]];
p=path;
return true;
}
int b[3]={0,0,0};
for(int i=0;i<8;i++)
++b[a[g[i]]-1];
int dd=8-max(max(b[0],b[1]),b[2]);
if(now+dd>maxd)
return false;
for(int i=0;i<8;i++)
{
int v=a[d[i][0]];
for(int j=0;j<6;j++)
a[d[i][j]]=a[d[i][j+1]];
a[d[i][6]]=v;
if(dfs(now+1,maxd,path+char(i+'A')))
return true;
v=a[d[i][6]];
for(int j=6;j>0;j--)
a[d[i][j]]=a[d[i][j-1]];
a[d[i][0]]=v;
}
return false;
}
int main()
{
while(scanf("%d",&a[0])&&a[0])
{
for(int i=1;i<24;i++)
scanf("%d",&a[i]);
//cout<<1<<endl;
ans=-1;
for(int maxd=0;;++maxd)
{
if(dfs(0,maxd,""))
{
if(maxd==0)
printf("No moves needed\n");
else
cout<<p<<endl;
printf("%d\n",ans);
break;
}
}
}
}
04-28 13:31