题目描述

通过拉扯使中间的数一样。

样例

输入样例：

1 1 1 1 3 2 3 2 3 1 3 2 2 3 1 2 2 2 3 1 2 1 3 3
1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3
0

输出样例：

AC
2
DDHH
2

(IDA*)

通过简单分析，我们可以发现每次拉扯只可以在中间多增加一个相同的数（拉进去一个出来一个，最理想状态为拉进去一个我们需要的数，扯出来不需要的数，所以每次最多增加一个目标数），所以估价函数设置为8减去中间最多的数个数就行了。

C++ 代码

#include <iostream>
#include <cstdio>
using namespace std;
int maze[30];
int rot[8][8]=//拉扯数的编号，输入顺序直接对应编号
{
    {1,3,7,12,16,21,23},//A
    {2,4,9,13,18,22,24},//B
    {11,10,9,8,7,6,5},//C
    {20,19,18,17,16,15,14},//D
    {24,22,18,13,9,4,2},//E
    {23,21,16,12,7,3,1},//F
    {14,15,16,17,18,19,20},//G
    {5,6,7,8,9,10,11}//H
};
int centre[10]={7,8,9,12,13,16,17,18};//中间数编号
int qqc[10]={5,4,7,6,1,0,3,2,8};//反向拉扯
int F[4];
char ans[1000];
int la;
int IDA(int lim,int las){
    F[1]=F[2]=F[3]=0;
    for(int i=0;i<8;i++) F[maze[centre[i]]]++;
    if(F[1]==8||F[2]==8||F[3]==8) return 1;//如果中间全为某一个数
    if(8-max(max(F[1],F[2]),F[3])>lim) return 0;//最优估价无法到达
    for(int i=0;i<8;i++)
        if(i!=qqc[las]){//拉过一次不反向拉
            int ttmp=maze[rot[i][0]];
            for(int j=1;j<7;j++) maze[rot[i][j-1]]=maze[rot[i][j]];//按照顺序移动
            maze[rot[i][6]]=ttmp;
            ans[la++]=i+'A';
            ans[la]=0;
            if(IDA(lim-1,i)) return 1;
            la--;
            ttmp=maze[rot[i][6]];
            for(int j=6;j>0;j--) maze[rot[i][j]]=maze[rot[i][j-1]];
            maze[rot[i][0]]=ttmp;
        }
    return 0;
}
int main(){
    while(1){
        scanf("%d",&maze[1]);
        if(!maze[1]) break;
        for(int i=2;i<=24;i++)
            scanf("%d",&maze[i]);
        for(int lim=0;;lim++)
            if(IDA(lim,8)){
                if(!lim) printf("No moves needed\n%d\n",maze[centre[0]]);
                else printf("%s\n%d\n",ans,maze[centre[0]]);
                break;
            }
        la=0;
    }
}