AcWing 181. 回转游戏

题目传送门

分析：

本题同样考察\(IDA*\)，每次有八种操作可以选择，一旦一开始选择了错误的方向，便可能搜索到很多无用的较深分支，因此可以在迭代加深的基础上使用估价函数。

分析最终状态，最终状态是中间八个数都是同一个数字，而每次操作都会使得中间八个数中的一个数出去，外面的一个数进来，也就是改变中间的一个数字。设x是中间八个数的众数，出现了k次，则至少要经过8 - k次操作才能够把中间所有的数都变成x，这就是估价函数的定义，即f = 8 - 众数出现的次数。

基本框架已经解决了，下面要解决的是如果存储和操作这个井字形棋盘。首先，按照题目的输入格式给这24个数编号，得到下面的图：

然后用个二维数组g存储各种操作会操作的数字，比如A会操作0,2,6,11,15,20,22，其他的也类似，最后得到一个八行七列的数组，每次操作只需要将对应的数组第一个数搬到末尾即可。同时，用center[8]存储中间的8个数的下标，用q存储编号0到23这24个数的具体数值。

这里还有个重要的剪枝，就是每次操作前要注意不能操作上一次的反操作，比如上一次进行了A操作，再次进行F操作就将棋盘还原了，肯定不是最优的操作，因此，用op数组存下各个操作的反操作编号，每次操作前判断下即可，dfs完恢复现场时也是用此次进行操作的反操作去恢复的。

代码的实现比较简单，唯一需要注意的是数组g存储的只是各个位置的元素在q中的编号，因此进行各种操作的时候，操作的是q数组里面的值，g数组里面的编号始终是不变的。

二、实现代码

#include 
using namespace std;
// IDA*  ：有层数控制的dfs(迭代加深)+估价函数,对迭代加深的优化，通过估价函数进行了剪枝
// https://blog.csdn.net/qq_30277239/article/details/105771948
// https://www.acwing.com/solution/content/46608/

int depth;     //迭代加深的深度,也就是步数上限
int q[24];     //棋盘
int path[100]; //操作的每一步动作，预估最多的操作是100步

// 八个方向下标
int g[8][7] = {{0, 2, 6, 11, 15, 20, 22},    // A
               {1, 3, 8, 12, 17, 21, 23},    // B
               {10, 9, 8, 7, 6, 5, 4},       // C
               {19, 18, 17, 16, 15, 14, 13}, // D
               {23, 21, 17, 12, 8, 3, 1},    // E
               {22, 20, 15, 11, 6, 2, 0},    // F
               {13, 14, 15, 16, 17, 18, 19}, // G
               {4, 5, 6, 7, 8, 9, 10}};      // H

// 中间八个位置格子号
int center[8] = {6, 7, 8, 11, 12, 15, 16, 17};

// 八个方向相反方向下标
int op[8] = {5, 4, 7, 6, 1, 0, 3, 2};

//估价函数，统计中间八个格子里，出现次数最多的是多少次
//估价函数的值，一定是小于等于真实的操作次数的
//每次操作，最多能引入一个相同的数字，所以，如果现在有k个不同的
//最少就需要8-k次操作才能保证将中间8个位置设置成全一样的数字
int f() {
    //函数内的数组，注意初始化,C++的特性是{0}表示所有数据为0，不是只第1个为0
    //用于计数1,2,3的数字个数
    int b[4] = {0};
    /*
      center[i]:八个中间格子的标识
      q[center[i]]:这八个中间格子在输入时的数字是什么
      b[q[center[i]]]:计数，1,2,3这三个数字每个出现过几次
     */
    for (int i = 0; i < 8; i++) b[q[center[i]]]++;
    int k = 0; //出现最多的是几次，（不是哪个数字出现最多，是最多是几次）
    for (int i = 1; i < 4; i++) k = max(k, b[i]);
    return 8 - k;
}

//拽
void push(int x) {
    //把头取出来,准备放到尾巴上
    // g[x][0]:第几号
    // q[g[x][0]]:这个号上现在是啥数字
    int t = q[g[x][0]];
    //把中间6个依次上移
    for (int i = 0; i < 6; i++) q[g[x][i]] = q[g[x][i + 1]];
    //把头上的数字放到尾巴上
    q[g[x][6]] = t;
}
/* 剪枝技巧
 最小字典序怎么办？其实这是因为出题人不想写Special Judge来判断,只是想最终判断一下字符串是否一致，就是因为他懒，懂吧~
 他懒，但是我们该怎么办呢？我们按啥顺序去搜索才能拿到最小字典序呢？
 一般的情况，我们只要按字典序来搜索，就可以顺理成章的拿到最终的最小字典序~
 就是每次在dfs搜索时，按从小到大的顺序来搜索就行啦

u   :走了几步了
pre :这一步，是由哪一步转化过来的，防止又走回去了
*/
bool dfs(int u, int pre) {
    int t = f();                     //计算当前状态的预计最少拽的次数
    if (u + t > depth) return false; //如果已经拽过的次数+未来最少拽的次数大于约定的次数，那么此路不通
    if (!t) return true;             //如果已经达到最终的目标，即f()=0，那么是成功完成
    //如果还没有完成目标，那么就枚举8个方向，从0-7，按字典序来枚举，看看这样拽行不行
    for (int i = 0; i < 8; i++) {
        //如果在此状态前的一个动作pre是由i这个动作转化而来，那么不能再转回去
        if (pre == op[i]) continue;
        //拽一下
        push(i);
        //记录第u次操作的操作动作，比如A C D E等等
        path[u] = i;
        //现在，本层我可以拽一下，那么这条路线是不是可以完成目标与我无关，与我的后继相关
        if (dfs(u + 1, i)) return true;
        //恢复现场
        push(op[i]);
    }
    return false;
}
int main() {
    //多组测试用例，如果某组测试用例的第1个是0，就停止程序
    //这种写法很棒，我没有想出来更好的实现方式
    while (cin >> q[0] && q[0]) {
        //第一个读取完了，其它的读取进来，共24个
        for (int i = 1; i < 24; i++) cin >> q[i];
        //可能不需要改变，中间8个本身就是一样的数字，最小移动步数为0
        depth = 0;
        //迭代加深
        while (!dfs(0, -1)) depth++;

        //如果最终最小移动步数为0，输出不需要移动
        if (!depth)
            cout << "No moves needed" << endl;
        else {
            //此题暗示我们，一定有解
            for (int i = 0; i < depth; i++)
                printf("%c", 'A' + path[i]);
            // cout << char('A' + path[i]);
            cout << endl;
        }
        //移动完成后，中间8个格子里的数字
        //中间那8个随便输入一个即可，内容都一样
        cout << q[6] << endl;
    }
    return 0;
}