🍑 算法题解专栏

---

🍑 回转游戏

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

给定 $8$ 种操作，分别为图中的 $$\begin{gathered} A \\ simH \end{gathered}$$。

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

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

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

输入格式

输入包含多组测试用例。

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

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

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

输出格式

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

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

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

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

输入样例：

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

---

import java.util.Scanner;/*0     12     3
4  5  6  7  8  9 1011    12
13 14 15 16 17 18 1920    2122    23*/public class Main
{static int N = 24;static int[] a = new int[N];static int[] path = new int[1000];
//	8个操作对应的 a 数组的下标值static int[][] op = { { 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 } };//	中心的八个数对应的下标值static int[] center = { 6, 7, 8, 11, 12, 15, 16, 17 };static int[] opposite = { 5, 4, 7, 6, 1, 0, 3, 2 };// 记录操作 i 的相反操作static boolean check(){for (int i = 0; i < 7; i++)if (a[center[i]] != a[center[i + 1]])return false;return true;}//	估价函数：每次移动顶多增加一个相同值，8 - 最大重复值个数 = 最优预估步数static int f(){int[] cnt = new int[4];for (int i = 0; i < 8; i++)cnt[a[center[i]]]++;int s = 0;for (int i = 1; i <= 3; i++)s = Math.max(s, cnt[i]);return 8 - s;}//	操作函数：将所有元素往头元素的方向移一位，头元素放在最后一位static void operation(int x){int t = a[op[x][0]];// 存头元素for (int i = 0; i < 6; i++)a[op[x][i]] = a[op[x][i + 1]];a[op[x][6]] = t;}
//	u 表示当前层数，maxd 表示IDA*的最大深度，pre表示前一个操作（避免做无用功）static boolean dfs(int u, int maxd, int pre){
//		IDA*加深if (u + f() > maxd)return false;
//		递归出口if (check())return true;//		枚举操作for (int i = 0; i < 8; i++){if (opposite[i] == pre)// 做相反的操作 == 白做continue;operation(i);// 进行 i 操作path[u] = i;if (dfs(u + 1, maxd, i))return true;operation(opposite[i]);}return false;}public static void main(String[] args){Scanner sc = new Scanner(System.in);while (sc.hasNext()){int a1 = sc.nextInt();if (a1 == 0)break;a[0] = a1;for (int i = 1; i < 24; i++)a[i] = sc.nextInt();int dep = 0;while (!dfs(0, dep, -1)){dep++;}if (dep == 0)System.out.println("No moves needed");else{for (int i = 0; i < dep; i++)System.out.printf("%c", 'A' + path[i]);System.out.println();}System.out.println(a[6]);}}
}