迭代搜索

http://poj.org/problem?id=2286

题意：

在如下图的棋盘中，摆放着8个1，8个2和8个3，
每一步你可以沿着A、B、C、D、E、F、G、H任意一个方向移动该字母所指的长块。
移出边界的小块会从另一端移进来。
如图，最左边的棋盘经过操作A，就会变成中间的棋盘布局，再进行操作C，就会变成右边的棋盘布局。
你需要设法使得最中间的8个格子的数字相同，问最少需要多少步。如何移动？

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
int ms[8][7] ={ 0, 2, 6,11,15,20,22,   //A操作对应的那一列在Map中的下标                  
                1, 3, 8,12,17,21,23,//B操作。。。下同                    
               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 R[8] = {5,4,7,6,1,0,3,2};  //各操作的相反操作在Ms中的行号                          
int mid[8] = {6,7,8,11,12,15,16,17}; //中间8块在Map中的下标               
int mm[24],op[50],dep;

int value(){//估计当前状态到目标状态的最少需要多少操作
    int a[3]={0,0,0};
    for(int i=0;i<8;i++)
        ++a[mm[mid[i]]-1];
    return 8-max(a[0],max(a[1],a[2]));
}
void move(int k){//进行（k+'A'）操作
    int t=mm[ms[k][0]];
    for(int i=0;i<6;i++)
        mm[ms[k][i]]=mm[ms[k][i+1]];
    mm[ms[k][6]]=t;
}
bool dfs(int Dep){
    if(dep==Dep)
        return false;
    for(int i=0;i<8;i++){
        move(i);
        op[Dep]=i;
        int v=value();
        if(v==0)
            return true;
        if(Dep+v<dep&&dfs(Dep+1))
            return true;
        move(R[i]);
    }
    return false;
}
int main(){
    while(~scanf("%d",&mm[0])&&mm[0]){
        for(int i=1;i<24;i++)
            scanf("%d",&mm[i]);
        dep=value();
        if(dep==0)
            printf("No moves needed
%d
",mm[6]);
        else{
            memset(op,0,sizeof(op));
            while(!dfs(0))
                ++dep;
            for(int i=0;i<dep;i++)
                printf("%c",'A'+op[i]);
            printf("
%d
",mm[6]);
        }
    }
    return 0;
}