python/TangDou/AcWing/IDAstar/181.md

## [$AcWing$ $181$. 回转游戏 ](https://www.acwing.com/problem/content/description/183/)

### 一、题目描述
如下图所示，有一个 `#` 形的棋盘，上面有 $1,2,3$ 三种数字各 $8$ 个。

给定 $8$ 种操作，分别为图中的 $A$∼$H$。

这些操作会 **按照图中字母和箭头所指明的方向**，把一条长为 $7$ 的序列循环移动 $1$ 个单位。

例如下图最左边的 `#` 形棋盘执行操作 $A$ 后，会变为下图中间的 `#` 形棋盘，再执行操作 $C$ 后会变成下图最右边的 `#` 形棋盘。

给定一个初始状态，请使用 **最少的操作次数**，**使 `#` 形棋盘最中间的 $8$ 个格子里的数字相同**。

<center><img src='https://www.acwing.com/media/article/image/2019/01/23/19_4ec33e321e-2286_1.jpg'></center>


**输入格式**
输入包含多组测试用例。

每个测试用例占一行，包含 $24$ 个数字，表示将初始棋盘中的每一个位置的数字，按整体从上到下，同行从左到右的顺序依次列出。

输入样例中的第一个测试用例，对应上图最左边棋盘的初始状态。

当输入只包含一个 $0$ 的行时，表示输入终止。

**输出格式**
每个测试用例输出占两行。

第一行包含所有移动步骤，每步移动用大写字母 $A$∼$H$ 中的一个表示，字母之间没有空格，如果不需要移动则输出 `No moves needed`。

第二行包含一个整数，表示移动完成后，中间 $8$ 个格子里的数字。

如果有多种方案，则输出 **字典序最小** 的解决方案。

**输入样例**：
```cpp {.line-numbers}
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
```

**输出样例**：
```cpp {.line-numbers}
AC
2
DDHH
2
```

### 二、题目解析

#### 1、限定步数+目标
本题同样考察$IDA*$，每次有八种操作可以选择，一旦 **一开始选择了错误的方向**，便可能搜索到 **很多无用的较深分支**，所以，一开始最好别陷的太深，否则将无法自拔，多么深刻的人生哲理~，因此可以在 **迭代加深的基础上使用估价函数**。

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

**基本框架** 已经解决了，下面要解决的是如果 **存储** 和 **操作** 这个井字形棋盘。

* 首先，按照题目的输入格式给这$24$个数编号，得到下面的图：(题目的输入顺序就是如此)

![](https://img2022.cnblogs.com/blog/8562/202203/8562-20220312134136313-973072875.png)

 * 用个二维数组 $\large g$ 存储 **各种操作** **会操作的数字**，比如$A$会操作$0,2,6,11,15,20,22$，其他的也类似，得到一个八行七列的数组，每次操作只需要 **将对应的数组第一个数搬到末尾** 即可。

* 用$\large center[8]$存储中间的$8$个数的下标
  
* 用$\large q$存储编号$0$到$23$这$24$个数的具体数值

* 用$\large op$数组存下各个操作的 **反操作编号**，每次操作前判断下不走回头路，`dfs`完恢复现场时也是用此次进行操作的反操作去恢复

### 三、实现代码
```cpp {.line-numbers}
#include <bits/stdc++.h>

using namespace std;

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

// 八个方向下标,共8行7列
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这三个数字每个出现过几次
     */
    int k = 0; // 出现最多的是几次，（不是哪个数字出现最多，是最多是几次）
    for (int i = 0; i < 8; i++) b[q[center[i]]]++;
    // 1,2,3 这三个数字，出现次数最多的是多少次？
    for (int i = 1; i < 4; i++) k = max(k, b[i]);
    // 估值：最少的操作次数
    return 8 - k;
}

// 拽,x∈[0,7],共8种操作
void drag(int x) {
    // g[x][0]:第几号
    // q[g[x][0]]:这个号上现在是啥数字

    // 每组7个数
    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;
}

/*
 Q:最小字典序怎么办？其实这是因为出题人不想写Special Judge来判断,只是想最终判断一下字符串是否一致，就是因为他懒，懂吧~
 他懒，但是我们该怎么办呢？我们按啥顺序去搜索才能拿到最小字典序呢？
 一般的情况，我们只要按字典序来搜索，就可以顺理成章的拿到最终的最小字典序~
 就是每次在dfs搜索时，按从小到大的顺序来搜索就行啦
u   :走几步了
pre :这一步，是由哪一步转化过来的，防止又走回去了
*/
bool dfs(int u, int pre) {
    int t = f();                     // 计算当前状态的预计最少拽的次数
    if (u + t > depth) return false; // 如果已经拽过的次数+未来最少拽的次数大于约定的次数，那么此路不通
    if (t == 0) return true;         // 如果已经达到最终的目标，即f()=0，那么是成功完成
    // 如果还没有完成目标，那么就枚举8个方向，从0-7，按字典序来枚举，看看这样拽行不行
    for (int i = 0; i < 8; i++) {
        // 如果在此状态前的一个动作pre是由i这个动作转化而来，那么不能再转回去
        if (pre == op[i]) continue;
        // 在此方向拽一下,使得地图变化
        drag(i);
        // 记录第u次操作的操作动作，比如A C D E等等
        path[u] = i;
        // 现在，本层我可以拽一下，那么这条路线是不是可以完成目标与我无关，与我的后继相关
        if (dfs(u + 1, i)) return true;
        // 恢复现场
        drag(op[i]);
    }
    return false;
}
int main() {
    while (scanf("%d", &q[0]) && q[0]) {                 // 判断输入是不是0的好办法
        for (int i = 1; i < 24; i++) scanf("%d", &q[i]); // 第一个读取完了，其它的读取进来，共24个

        // 可能不需要改变，中间8个本身就是一样的数字，最小移动步数为0
        depth = 0;
        // 迭代加深
        while (!dfs(0, -1)) depth++;

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

####　1、$Q:A*$可以做本题吗？$A*$怎么保证输出 **字典序** ？

答：$A*$算法求字典序比较麻烦，因为 优先队列中 是 **按估价函数排序** **而非字典序排序**，所以 **除非将步数最小的所有方案全部求出，否则是无法求出字典序的**。

本题用$IDA*$比较好。


#### 2、顺序与复杂度

每步枚举 $7$ 种操作（最优性剪枝，**除去上一步的逆操作**），若总步数为 $k$，则复杂度为 $O(7^k)$。玄学猜想，操作步数不会太多，但会出现 **极深分支**，因此可使用 **迭代加深**

#### 3、最小字典序
每步按可选操作的 **最小字典序枚举** 可得到 **最小字典序操作序列**（相同层数，最小字典序最先搜到）

#### 4、估价函数
每步会从中间移走一个数字，并移入一个数字，记中间最多数字的个数为 $cnt$，则至少需 $8−cnt$ 步才能使中间全部变为同一数字，因此估价函数可定为 $f(s)=8−cnt$

#### 5、坐标打表
**对于方格较少的不规则图形**，**若可选操作的方式类似，仅目标方格不同，存储每种操作的目标方格映射能有效简化代码**

#### 6、总结
**迭代加深** 适用于答案层数 **较浅**，但某些分支特别深的问题，若估价函数容易找到，可搭配 $A∗$ 使用，此时变为 $IDA∗$，它能求出 **最小步数** 和 **最小字典序操作序列**