如下图所示，有一个 # 形的棋盘，上面有 三种数字各 个。
给定 种操作，分别为图中的 。
这些操作会按照图中字母和箭头所指明的方向，把一条长为 的序列循环移动 个单位。
例如下图最左边的 # 形棋盘执行操作 后，会变为下图中间的 # 形棋盘，再执行操作 后会变成下图最右边的 # 形棋盘。
给定一个初始状态，请使用最少的操作次数，使 # 形棋盘最中间的 个格子里的数字相同。
1
输入格式
输入包含多组测试用例。
每个测试用例占一行，包含 个数字，表示将初始棋盘中的每一个位置的数字，按整体从上到下，同行从左到右的顺序依次列出。
输入样例中的第一个测试用例，对应上图最左边棋盘的初始状态。
当输入只包含一个 的行时，表示输入终止。
输出格式
每个测试用例输出占两行。
第一行包含所有移动步骤，每步移动用大写字母 中的一个表示，字母之间没有空格，如果不需要移动则输出 No moves needed。
第二行包含一个整数，表示移动完成后，中间 个格子里的数字。
如果有多种方案，则输出字典序最小的解决方案。
输入样例：
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输出样例：
AC
2
DDHH
2思路
题意给一个#号序列, 可以对其做8种操作, 使得中间8个数相同, 要求找到最小操作数。
考虑爆搜。 搜索顺序： u为当前操作步数, depth为最大深度, last为上一步操作记录。 每次可以对其操作A~H, 用path数组记录操作。
剪枝优化：
- 需要按照字典序, 那就按照A~H的顺序进行操作
- 我们每次操作最好情况下是将两个相同变成三个相同, 故每次改变一个格子, 题目要求让中间8个数相同, 可以设定当前最多相同的数字 num, 其数量为s, 损失函数为 8 - s, 即剩下多少步让该数字变成8个。
操作比较繁琐, 我们可以将#编号如下：
0 1
2 3
4 5 6 7 8 9 10
11 12
13 14 15 16 17 18 19
20 21
22 23然后声明一个8*6的op数组, 记录每个操作对应的下标。还有一个 center 数组, 记录中间8个值的下标, 然后再实现operate操作函数即可。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 8, M = 25;
int op[N][N] = {
{0,2,6,11,15,20,22},
{1,3,8,12,17,21,23},
{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 opposite[8] = {5, 4, 7, 6, 1, 0, 3, 2};
int center[8] = {6,7,8,11,12,15,16,17};
int q[M];
int path[100];
void operate(int x)
{
int t = q[op[x][0]];
for(int i = 0; i < 6; i++) q[op[x][i]] = q[op[x][i + 1]];
q[op[x][6]] = t;
}
int f()
{
static int sum[8];
memset(sum, 0, sizeof sum);
int s = 0;
for(int i = 0; i < 8; i++)
sum[q[center[i]]]++;
for(int i = 1; i < 4; i++) s = max(s, sum[i]);
return 8 - s;
}
bool dfs(int u, int depth, int last)
{
if(u + f() > depth) return false;
if(f() == 0) return true;
for(int i = 0; i < 8; i++)
{
if(opposite[i] == last) continue;
operate(i);
path[u] = i;
if(dfs(u + 1, depth, i)) return true;
operate(opposite[i]);
}
return false;
}
int main()
{
while(cin >> q[0], q[0])
{
for(int i = 1; i < 24; i++) cin >> q[i];
int depth = 0;
while(!dfs(0,depth, -1)) depth++;
if(!depth) cout << "No moves needed";
else
{
for(int i = 0; i < depth; i++) cout << char(path[i] + 'A');
}
cout << endl << q[center[0]] << endl;
}
return 0;
}