You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

113 lines
4.8 KiB

2 years ago
#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;
}