排版不咋地，凑合看罢——2022.5.2注
这道题最难的其实不是估价函数设计，而是怎么高效并且简洁地进行状态转换。
这个问题非常令人头疼，因为棋盘的形状很奇怪，是一个井字形。
最朴素的方法当然是直接用二维数组 / 开四个数组存储，至于这样能不能过我也不清楚好像能过。因为我第一次看这道题的时候不知道脑子抽了哪根筋用了四个十进制数存储，导致后续操作极其麻烦，最后常数复杂度过高TLE， IDA* 都救不了它，因为代码太长就不粘在这里了，想看的可以去看 测评记录 #14498。
在看了 AcWing 的题解后，我找到了一种非常巧妙的思路。
状态存储与转换
一般在处理状态时，我们都是将棋盘存储下来，然后按照操作模拟变换，为了方便可能会想到将棋盘按照操作需要的方式存储，也就是每一行每一列分别存储，这样在操作时直接遍历对应数组修改就行。这样做的缺点是读入时的不方便以及修改时可能要修改好几个数组（因为棋盘之间有交叉）。
寻找操作的共同点，可以看出它们都是对于某一行或某一列遍历修改。
为了方便表达，以下用 表示以输入顺序存储的数组。
为了实现对某一行或某一列的遍历，可以类比对树和图进行遍历的思想，在对其进行遍历时，我们并没有按照在数组中存储的顺序直接遍历，而是按照节点之间相互连接的顺序。在这里对数组 的遍历也是如此，只不过这里是按照同行或同列进行遍历。为此可以建立对某一个操作的遍历序列。进一步地，对于相反的操作，可以用一个逆序数列存储。
可能还是比较抽象，我演示一下， 中的元素下标对应到棋盘上如下。
1 2
3 4
5 6 7 8 9 10 11
12 13
14 15 16 17 18 19 20
21 22
23 24
那么对于 A 操作的遍历序列 可以这么写：
这样，我们就可以把进行 A 操作时对 的遍历转化为对 的遍历，也就是说，我们对 逐一进行遍历，并依据其中存储的对应在 中的下标对 进行修改。
依照这样的思路，不难写出其他所有操作的遍历序列。
int op_index[8][7] = {
{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
};
这样，我们可以把所有的操作写成一个函数。通过控制调用时参数的传递，令其访问这个数组中不同的操作的遍历序列。为了方便操作，可以将操作 A ~ H 分别映射到下标 0 ~ 7 进行处理。
void operate(const int & op)
{
int t = board[op_index[op][0]];
for (int i = 0; i < 7; i++) {
board[op_index[op][i]] = board[op_index[op][i + 1]];
}
board[op_index[op][6]] = t;
}
估价函数设计
我们已经把状态的存储与转换问题巧妙地解决了，回顾题目，作为一道 IDA* 题，估价函数自然是必不可少的。
基本思想自然是通过估计未来代价来估计当前路径总代价，当代价过大无法找到最优解时及时回溯。对未来代价的估计肯定不能大于未来实际代价。那么对于这道题我们要估计的 “ 未来代价 ” 就是当前状态到终态的最少步数。不难想出，可以统计出中间一圈数字中个数最多的数字，把它的个数记作 ，让 作为对未来步数的估计，这个步数肯定是最少的。为了方便对中间进行遍历和统计，可以采用和之前一样的思想，用另一个数组 存储所有位于中间的数字在 中的下标。
搜索代码
#include <cstdio>
#include <cstring>
using namespace std;
/*
* 1 2
* 3 4
* 5 6 7 8 9 10 11
* 12 13
* 14 15 16 17 18 19 20
* 21 22
* 23 24
*/
int board[25];
const int A = 0, B = 1, C = 2, D = 3, E = 4, F = 5, G = 6, H = 7;
int op_index[8][7] = {
{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 center[8] = {7, 8, 9, 12, 13, 16, 17, 18};
int opposite[9] = {F, E, H, G, B, A, D, C, -1}; // 存储相反操作
const int max(const int & a, const int & b)
{
return (a > b) ? a : b;
}
void operate(const int & op)
{
int t = board[op_index[op][0]];
for (int i = 0; i < 7; i++) {
board[op_index[op][i]] = board[op_index[op][i + 1]];
}
board[op_index[op][6]] = t;
}
int f()
{
int cnt[4] = {0};
for (int i = 0; i < 8; i++) {
cnt[board[center[i]]]++;
}
int ans = 0;
for (int i = 1; i <= 3; i++) {
ans = max(ans, cnt[i]);
}
return 8 - ans;
}
int maxdep = 1, minstep = 0x3f3f3f3f;
int ans[1000];
int state[1000];
int ans_t;
bool dfs(int dep, int last)
{
if (f() == 0) { // 判断是否到达终态
if (minstep > dep) {
minstep = dep;
memcpy(ans, state, sizeof(state));
ans_t = dep;
}
return true;
}
if (dep == (maxdep + 1)) { // 没有找到解，搜索失败
return false;
}
if (dep + f() > maxdep || dep + f() > minstep) { // 当前分支代价过大不可行，或找到的解不会更优
return false;
}
for (int op = A; op <= H; op++) {
if (op == opposite[last]) { // 防止回搜
continue;
}
operate(op);
state[dep + 1] = op; // 记录操作
if (dfs(dep + 1, op)) // 如果找到解就直接回溯
return true;
operate(opposite[op]); // 还原现场
}
return false;
}
void init()
{
maxdep = 1, minstep = 0x3f3f3f3f;
ans_t = 0;
}
int main()
{
// freopen("in.in", "r", stdin);
while (scanf("%d", &board[1]) != EOF && board[1] != 0) {
for (int i = 2; i <= 24; i++) {
scanf("%d", &board[i]);
}
if (!f()) {
printf("No moves needed\n");
int cnt[4] = {0};
for (int i = 0; i < 8; i++) {
cnt[board[center[i]]]++;
}
int maxn = 0;
for (int i = 0; i < 8; i++) {
if (cnt[maxn] < cnt[board[center[i]]]) {
maxn = board[center[i]];
}
}
printf("%d\n", maxn);
init();
continue;
}
maxdep = f();
while (maxdep < minstep && !dfs(0, 8)) {
maxdep++;
}
for (int i = 1; i <= ans_t; i++) {
printf("%c", ans[i] + 'A'); // 映射回所有的操作
}
printf("\n");
int cnt[4] = {0};
for (int i = 0; i < 8; i++) {
cnt[board[center[i]]]++;
}
int maxn = 0;
for (int i = 0; i < 8; i++) {
if (cnt[maxn] <= cnt[board[center[i]]]) { // 不加 = 的话在 AcWing 会 WA
maxn = board[center[i]];
}
}
printf("%d\n", maxn);
init();
}
return 0;
}