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
--
