UVa 连结 : https://reurl.cc/8OKXo
题目简易说明
这题是要解一个 2x2x2 的二阶魔术方块 ( 6 面、6 颜色 )
会给定一个魔术方块的状态
然后要找出可以还原魔术方块的最少步骤是多少
输入面的顺序为 : Top , Front, Right , Bottom, Back , Left
且每面的初始色 : White, Red , Yellow, Blue , Orange, Green
我的解法一
参考维基百科 : https://reurl.cc/Ea3Qn
二阶魔方最有只有 3674160 种状态
而且最多只要 14 个步骤就能将方块还原
以下是需要转动步骤的状态数:
所需步骤 状态数量
0 1
1 6
2 27
3 120
4 534
5 2256
6 8969
7 33058
8 870072
9 360508
10 930508
11 1350852
12 782536
13 90280
14 276
所以我就将这 3674160 利用 BFS 由上到下暴力列举出来
列举方法:
以 Front、Right、Bottom 三面相交的那块方块为基准点
可以做的转动只有 6 种 : U Up L Lp B Bp
U : Top 那面面对自己做 顺 时针旋转
Up : Top 那面面对自己做 逆 时针旋转
L : Left 那面
B : Back 那面
就从步骤 0 开始 ( 方块还原状态 )
依序做 6 种转动，并得到步骤 1 的方块状态
直到步骤 14
其中可以用一些规则去避免重复 ( 不然 6^14 = 7百多亿 )
1. L L L = Lp ( 转 270度 = 转 -90度 )
2. 若上一步骤是 L，则这一步骤就不能为 Lp ( 做白工 )
3. L L = Lp Lp ( 我选择遇到 Lp Lp 就不要做 )
但是除了以上三种，还是会有很多重复是抓不到的
所以我将每种状态放入 Hash Table 中
( C++ unordered_multimap )
key : 根据方块的状态 (每一面颜色) 所 "乱凑" 出来的数值
value : 该方块的资讯 (状态、还原所需步骤等等)
每新算出一种状态 ( 不违反上面 3 个规则 )
还要去 Hash Table 中检查有没有重复，没有的话就同样丢入 Table 中
最后
只要把题目输入的方块状态同样依据上面算 key 的方法算出来
再去 Hash Table 找，并得到该方块的资讯，就可以知道最短步骤
缺点
这样太慢，UVa 时限是 3 秒，我光是跑完列举就要大概 10 秒了
其中大部分的时间都是花在 Hash Table 查找
( 因为 hash 会碰撞，所以只能用 equal_range(key) 去查找，但还是剖慢)
我的解法二
为了避免掉 Hash Table 查找
所以直接对题目给的方块状态去做暴力 BFS
不过这次就不使用 Hash Table 来储存找到的状态
也不检查除了上面 3 个规则以外是否还有重复的
这样会比较快
但是因为数量增长太大，也是会很慢而且内存还会爆掉
问题
请问各位大大有没有什么更快的做法呢?
UVa 上的数据很多人都可以在 1 秒内 AC，但我一职 TLE ...
或是我还有哪里可以再加快的呢?
谢谢
附上写得不好的程式码 ( 解法一 )
https://pastebin.com/embed_iframe/c2e3idba