UVa 11007 : Mini Cube

題目 : UVa Link

本題是要解一個二階魔術方塊 ( 2x2x2 )，題目會給定一個魔術方塊的狀態，要求出復原方塊的最少步驟是多少

輸入六個面，依序為 Top、Front、Right、Bottom、Back、Left
而復原狀態的方塊顏色依上面的順序為 White、Reg、Yellow、Blue、Orange、Green
並且每一面輸入字串的順序依照下圖 :

測資
Input :

2

GGGG
WWBB
OORR
YYYY
BBWW
RROO

WRRG
WORO
BGBW
YYOG
BORY
GYWB

Output :

2
6

想法

參考Wiki，可以得知二街魔術方塊只有

$ \frac{ 8! 3^7 }{ 24 } = 7! 3^6 = 3674160 $

且最多 14 步r就可以還原魔術方塊，如下表

旋轉次數	狀態數量
0	1
1	6
2	27
3	120
4	534
5	2256
6	8969
7	33058
8	114149
9	360508
10	930588
11	1350852
12	782536
13	90280
14	276

再來就是對方塊的一些操作
( 注意旋轉時的方式是依照將該面面對自己的順時針方向與逆時針方向 )

代號	意思	說明
F	Front face 正面	面向你的那一面順時針轉 90 度
R	Right face 右面	右邊那一面順時針轉 90 度
B	Back face 背面	背面順時針轉 90 度
L	Left face 左面	左面順時針轉 90 度
U	Up face 上面	上面順時針轉 90 度
D	Down face 底面	下面順時針轉 90 度

若在代號後面加上 p 的話，代表那個一面 逆時針轉90度
例 : Lp 就是 Left face 逆時針轉 90 度
因此總共有 12 種旋轉面的方式

接下來還有轉動整個方塊的操作

代號	說明
X	整個方塊依照 Up 的方向轉動 90 度
Y	整個方塊依照 R 的方向轉動 90 度
Z	整個方塊依照 F 的方向轉動 90 度

同樣的若是在代號後面加上 p 的話，代表 旋轉相反方向
例 : Yp 就是將整個方塊依照 Rp 的方向轉動 90 度
總共有 6 種旋轉整個方塊的方式

但是為了方便辨識方塊，我們可以將方塊統一定點到一個固定的方位
例如，將復原的方塊依照上述的方向面對自己 ( Top 是 White、Front 是 Red、Right 是 Yellow )
可以發現 Front、Bottom 與 Right 的那個交界邊角，顏色依序為 Front = Red、Bottom = Blue 與 Right = Yellow

因此我們就令這塊邊角為基準點來轉動方塊的面的話，就只剩下 6 種面的操作

代號	意思	說明
B	Back face 背面	背面順時針轉 90 度
Bp	Back face 背面	背面逆時針轉 90 度
L	Left face 左面	左面順時針轉 90 度
Lp	Left face 左面	左面逆時針轉 90 度
U	Up face 上面	上面順時針轉 90 度
Up	Up face 上面	上面逆時針轉 90 度

另一個設立基準地的好處是，題目給的方塊不一樣會剛好就是我們所存的方向
因此我們只要利用轉動方塊的操作，就可以把方塊調整到與剛好契合基準點

解法一

我們可以把全部 3674160 種方塊的可能性利用 BFS 全部列舉出來
從還原狀態 step 0 ( 旋轉次數 0 ) 開始，對方塊做 6 種面的操作 ( L、Lp、U、Up、B、Bp )
就可以得到 step 1 ( 旋轉次數 1 ) 的 6 個情況，其中每一種情況同樣地在操作 6 個面的操作
得到 $ 6^6 = 36 $ 種 step 2 的情況，依序做下去直到 step 14
不過可以發現從 step 2 開始，就會有重複的情況發生，有 36 - 27 = 9 種
step 14 = $ 6^14 = 78364164096 $ ，可以發現和真正的狀態數量 276 差了十萬八千里

因此，我們要來找一下會重複的規則:

1. 若此步驟做了與上一步驟相反方向的操作，那就是多餘的。
   例 : 上一步是 L，那這步驟就不能再做 Lp 了
2. 連續做 2 次同樣的操作就會等於連續做 2 次相反的操作。
   例 : L L 就會等於 Lp Lp，所以我選擇遇到逆時針 ( p ) 的 2 次操作就不要做
3. 連續做 3 次同樣的操作就等同於做 1 次相反的操作。
   例 : L L L 就等同於 Lp，注意只有 L、U、B 才有可能會用到這個規則，因為 p 被規則二給去掉了

有了這三個規則，我們每一次對該狀態去做 6 次面操作的時候，就可以去檢查有沒有符合這三個規則
若有的話就不做這個面操作

但若各位有真的去試試看的話，會發現在 step 5 的時候，又會發生重複的情況，會等於 2376 而非 2256
那這就是沒辦法用規則去發現的重複狀況，所以我們會需要將之前成功列舉過的狀態紀錄起來
每當成功的做了某個面操作後，還要去檢查有沒有和之前列舉過的狀態重複

我是使用 Hash Table 來記錄成功列舉過的狀態，由於可能會發生 Collision，所以不能只有單純地存 key 值而已
還是需要把該相同 key 值的狀態都記錄下來，若又有一新的狀態的 key 值相同，則去和那些狀態檢查
因此我選用 C++ unordered_multimap，期待搜索可以為 O(1)

• key : 利用方塊的 6 個面 ( 每個面有 4 格 ) 去做 hash function。(depend on your implement)
• value : 該方塊的 Reference。( 這是一個不好的習慣，我為了減少記憶體而已，而且我也確保該方塊記憶體不會更動 )

整理一下解法一的步驟:

首先，從 step 0 開始，對每個狀態依序去做 6 種面的操作，然後

1. 檢查 3 個重複規則，若符合，就去掉這個操作
2. 通過 3 個規則後，對方塊做該操作
3. 對此新的狀態去計算他的 hash 值
4. Search the hash table，若發先該 hash 值已經存在，則進入步驟 5，否則進入步驟 7
5. 利用 unordered_multimap 的 equal_range(key) 去獲得所有 hash value = key 的方塊 list
6. 一一去比對方塊 list 與此新狀態是否有相同狀態，若相同，則去掉此狀態，若否，則加入此狀態
7. 若還沒做完 6 的面操作，則繼續下一種操作，若做完了，就進入下一個 step，直到 step 14

再來，全部都列舉完後，就可以來解題目了

1. 讀進題目給的方塊狀態
2. 將該狀態歸位到對齊基準點
3. 算出此已經對齊的狀態的 hash value
4. 搜尋 hash table，並得到方塊 list
5. 一一比對方塊 list，找到與此狀態相同的那個方塊，就可以知道他是 step 幾，這就是他的最少步數

缺點

若各位有試過的話，可以發現在列舉的時候就會很耗時間了，UVa 只有 3 秒，我本人實測列舉完就要 12 秒了
所以一定會 TLE，因此我們還要想想其他可以改進的方法，有幾個方向可以去改進:

1. 大部分的時間都是耗在 equal_range() 這個 method
2. 可以發現我們列舉大部分的狀態都是在 step 11 附近，若我們可以避開這裡，也就是不要做這麼多狀態的話
   時間可以加快很多

解法二

解法二就是解決了解法一的第二個缺點

首先，我們一樣要從還原狀態的方塊開始列舉，和解法一一樣，不過我們只列舉到 step 7 ( step 8 也可以 )
因此我們就只需紀錄 step 0 ~ step 7 的狀態共 44971 種，想比原本的 3674160 少了一脫拉庫

然後對於題目所輸入的方塊狀態，先把他歸位對齊基準點後，再對他去做列舉 step 0 (初始狀態) ~ step 7
不過和上面的列舉不同的是 : 除了 3 個規則，不去檢查有沒有之前的是重覆的
因此會比原本的狀態還要多一些，但也不會多太多

旋轉次數	有檢察之前的	沒檢查
0	1	1
1	6	6
2	27	27
3	120	120
4	534	534
5	2256	2376
6	8969	10572
7	33058	47040
Total	44971	60676

因此解法二的整個過程如下 :

1. 先用還原狀態列舉出完整的 step 0 ~ step 7 所有狀態，且要用 Hash Table 去檢查有沒有重複
2. 讀入題目給定的方塊狀態，然後將它對其基準點歸位 ( 用 P 表示此已經對齊的狀態 )
3. 計算 P 的 hash value，檢查有沒有再 Hash Table 中
   若有，得到 Table 中存的方塊資訊 –> step = k，那麼 P 的最短步數就是 k ( k <= 7 )
   若沒有，進行步驟 4
4. 對 P 列舉出 step 1 ~ step 7 的所有狀態 ( P 就是 step 0 )
   注意不需要再額外用 Hash Table 檢查有沒有重複
   對於每一狀態，去做 6 種面的操作，且要檢查有沒有符合 3 個規則
   若符合，則去除這個操作
   若不符合，就直接記錄起來，並進行步驟 5，不用再用另一個 Hash Table 去檢查有沒有和之前的重複
5. 對於每個新的合法狀態 ( 符合 3 個規則 )，要去計算他的 hash 值，檢查有沒有再 Hash Table 中
   若有，得到 Table 中存的方塊資訊 –> step = k，且目前列舉的 step = t，那麼 P 的最短步數就是 S = k + t (8<=S<=14)
   若沒有，則回到步驟 4 進行下一個面操作
6. 找到 P 的最短步數後，就可以回到步驟 2 讀入下一個題目了

簡單來說，就是用 雙向 BFS 去加速，對方塊還原狀態做一次 BFS 列舉 step 0 ~ step 7 得到 Hash Table
之後再針對每個題目輸入的待解狀態做一次 BFS 列舉 step 0 ~ step 7，且邊做邊檢查有沒有在剛剛的 Hash Table 中

這樣就可以很有效的加速了

程式碼

這份程式碼寫得很冗長，可以看看就好，參考一下
最下面有稍微對程式碼的解說

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

class Face
{
public:
	enum { W = 0, R, B, Y, O, G };

	using Type = uint16_t;

	Face() : data{ 0 } {}

	Face(const string &input) : data{ 0 }
	{
		for (int i = 0; i < SIZE; ++i)
		{
			switch (input[i])
			{
			case 'W':
				data += (W << (i * MASK));
				break;
			case 'R':
				data += (R << (i * MASK));
				break;
			case 'B':
				data += (B << (i * MASK));
				break;
			case 'Y':
				data += (Y << (i * MASK));
				break;
			case 'O':
				data += (O << (i * MASK));
				break;
			case 'G':
				data += (G << (i * MASK));
				break;
			}
		}
	}

	unsigned operator[](int idx)
	{
		return (data & M[idx]) >> (idx * MASK);
	}

	unsigned operator[](int idx) const
	{
		return (data & M[idx]) >> (idx * MASK);
	}

	void set(int idx, Type c)
	{
		data -= (data & M[idx]);

		data += (c << (idx * MASK));
	}

	bool operator==(const Face &f) const
	{
		return data == f.data;
	}

	bool operator!=(const Face &f) const
	{
		return data != f.data;
	}

	void rotation(int i)
	{
		if (i == 0)
		{
			auto tem = (*this)[0];
			auto tem2 = (*this)[1];
			set(0, (*this)[3]);
			set(1, (*this)[2]);
			set(2, tem2);
			set(3, tem);
		}
		else if (i == 1)
		{
			// 3 2 1 0 -> 1 3 0 2

			auto tem = (*this)[0];
			set(0, (*this)[2]);
			set(2, (*this)[3]);
			set(3, (*this)[1]);
			set(1, tem);
		}
		else
		{
			// 3 2 1 0 -> 2 0 3 1
			auto tem = (*this)[0];
			set(0, (*this)[1]);
			set(1, (*this)[3]);
			set(3, (*this)[2]);
			set(2, tem);
		}
	}

	Type get_data(void) const
	{
		return data;
	}

private:

	enum {MASK = 4, SIZE = 4};
	static const vector<Type> M;

	Type data;
};

const vector<Face::Type> Face::M{ 0xF,0xF0, 0xF00, 0xF000 };

class Cube
{
	enum {TOP = 0, FRONT, RIGHT, BOTTOM, BACK, LEFT};
	enum {_1 = 0, _2 = 1, _3 = 2, _4 = 3};

public:
	using Type = unsigned int;

	Cube() : data{ Face{"WWWW"}, Face{"RRRR"}, Face{"YYYY"}, Face{"BBBB"}, Face{"OOOO"}, Face{"GGGG"} },repeat_cnt{ 0 }, last_step{ 0 }, step_cnt{ 0 } {} //"WWWW", "RRRR", "YYYY", "BBBB", "OOOO", "GGGG"

	Cube(const vector<string> &input) : repeat_cnt{ 0 }, last_step{ 0 }, step_cnt{ 0 }
	{
		for (int i = 0; i < 6; ++i)
			data.push_back(Face{ input[i] });

		set_position();
	}

	Cube(const Cube &c) : data{ c.data }, repeat_cnt{ c.repeat_cnt }, last_step{ c.last_step }, step_cnt{ c.step_cnt } {}

	Cube(Cube &&c) : data{ move(c.data) }, repeat_cnt{ c.repeat_cnt }, last_step{ move(c.last_step) }, step_cnt{ move(c.step_cnt) } {}

	bool operator==(const Cube &c) const
	{
		for (int i = 0; i < 6; ++i)
			if (data[i] != c.data[i])
				return false;
		return true;
	}

	unsigned int hash(void) const
	{
		auto k = (data[0].get_data() << 8) + data[1].get_data() + (data[2].get_data() << 4);
		auto t = (data[5].get_data() << 8) + data[4].get_data() + (data[3].get_data() << 4);

		return  k ^ t;
	}

	void flip(int i)
	{
		switch (i)
		{
		case 1:
			L();
			break;
		case 2:
			Lp();
			break;
		case 3:
			U();
			break;
		case 4:
			Up();
			break;
		case 5:
			B();
			break;
		case 6:
			Bp();
			break;
		default:
			cout << "flip error" << endl;
			break;
		}

		add_path(i);
	}

	Cube flip_cp(int i) const
	{
		Cube c{ *this };

		c.flip(i);

		return c;
	}

	void add_path(int i)
	{
		if (last_step == i)
			++repeat_cnt;
		else
			repeat_cnt = 1;

		last_step = i;
		++step_cnt;
	}

	int get_last_path(void) const
	{
		return last_step;
	}

	int get_repeat_cnt(void) const
	{
		return repeat_cnt;
	}

	int get_step(void) const
	{
		return step_cnt;
	}

private:
	
	vector<Face> data;
	unsigned char repeat_cnt;
	unsigned char last_step;
	unsigned char step_cnt;

	void set_position(void)
	{
		static const vector<vector<int>> fc{ {TOP,LEFT,BACK},{TOP,RIGHT,BACK},{TOP,LEFT,FRONT},{TOP,RIGHT,FRONT},
			{BOTTOM,LEFT,FRONT},{BOTTOM,RIGHT,FRONT},{BOTTOM,LEFT,BACK},{BOTTOM,RIGHT,BACK} };
		static const vector<vector<int>> idx{ {_1,_1,_2},{_2,_2,_1},{_3,_2,_1},{_4,_1,_2},
			{_1,_4,_3},{_2,_3,_4},{_3,_3,_4},{_4,_4,_3 } };

		Cube c{};
		vector<unsigned> base = { c.data[FRONT][_4],c.data[RIGHT][_3] ,c.data[BOTTOM][_2] };

		int i, k, t;
		unsigned color;
		int ans = -1;

		for (i = 0; i < 8; ++i)
		{
			vector<bool> ok(3, false);

			for (k = 0; k < 3; ++k)
			{
				color = data[fc[i][k]][idx[i][k]];

				for (t = 0; t < 3; ++t)
					if (color == base[t])
						ok[t] = true;
			}

			if (ok[0] && ok[1] && ok[2])
			{
				ans = i;
				break;
			}
		}

		if (ans == -1)
		{
			cout << "position error" << endl;
			return;
		}

		rotation(ans);

		set_corner(fc[5], idx[5], c.data[BOTTOM][_2]);
	}

	void rotation(int i)
	{
		vector<int> v(2);

		switch (i)
		{
		case 0:
			v[0] = 0;
			v[1] = -1;
			break;
		case 1:
			v[0] = -1;
			v[1] = -1;
			break;
		case 2:
			v[0] = 1;
			v[1] = -1;
			break;
		case 3:
			v[0] = 99;
			v[1] = -1;
			break;
		case 4:
			v[0] = 1;
			v[1] = 99;
			break;
		case 5:
			v[0] = 99;
			v[1] = 99;
			break;
		case 6:
			v[0] = 0;
			v[1] = 99;
			break;
		case 7:
			v[0] = -1;
			v[1] = 99;
			break;
		}

		if(v[0] != 99)
			X(v[0]);
		if (v[1] != 99)
			Y(v[1]);
	}

	void set_corner(const vector<int> &fc, const vector<int> &idx, unsigned bot_color)
	{
		// {BOTTOM,RIGHT,FRONT}
		// {_2,_3,_4}
		int y = -1;

		for(int i=0;i<3;++i)
			if (data[fc[i]][idx[i]] == bot_color)
			{
				y = i;
				break;
			}

		if (y == 1)
		{
			Z(1);
			X(1);
		}
		else if (y == 2)
		{
			Y(-1);
			X(-1);
		}
	}

	void L(void)
	{
		// left
		data[LEFT].rotation(1);


		// top
		auto tem = data[TOP][_1];
		auto tem2 = data[TOP][_3];

		data[TOP].set(_1, data[BACK][_4]);
		data[TOP].set(_3, data[BACK][_2]);

		// back
		data[BACK].set(_4, data[BOTTOM][_1]);
		data[BACK].set(_2, data[BOTTOM][_3]);

		// bottom
		data[BOTTOM].set(_1, data[FRONT][_1]);
		data[BOTTOM].set(_3, data[FRONT][_3]);

		// front
		data[FRONT].set(_1, tem);
		data[FRONT].set(_3, tem2);
	}

	void Lp(void)
	{
		// left
		data[LEFT].rotation(-1);

		// top
		auto tem = data[TOP][_1];
		auto tem2 = data[TOP][_3];

		data[TOP].set(_1, data[FRONT][_1]);
		data[TOP].set(_3, data[FRONT][_3]);

		// front
		data[FRONT].set(_1, data[BOTTOM][_1]);
		data[FRONT].set(_3, data[BOTTOM][_3]);

		// bottom
		data[BOTTOM].set(_1, data[BACK][_4]);
		data[BOTTOM].set(_3, data[BACK][_2]);

		// back
		data[BACK].set(_4, tem);
		data[BACK].set(_2, tem2);

	}

	void U(void)
	{
		// top
		data[TOP].rotation(1);

		// front
		auto tem = data[FRONT][_1];
		auto tem2 = data[FRONT][_2];

		data[FRONT].set(_1, data[RIGHT][_1]);
		data[FRONT].set(_2, data[RIGHT][_2]);

		// right
		data[RIGHT].set(_1, data[BACK][_1]);
		data[RIGHT].set(_2, data[BACK][_2]);

		// back
		data[BACK].set(_1, data[LEFT][_1]);
		data[BACK].set(_2, data[LEFT][_2]);

		// left
		data[LEFT].set(_1, tem);
		data[LEFT].set(_2, tem2);
	}

	void Up(void)
	{
		// top
		data[TOP].rotation(-1);

		// front
		auto tem = data[FRONT][_1];
		auto tem2 = data[FRONT][_2];

		data[FRONT].set(_1, data[LEFT][_1]);
		data[FRONT].set(_2, data[LEFT][_2]);

		// left
		data[LEFT].set(_1, data[BACK][_1]);
		data[LEFT].set(_2, data[BACK][_2]);

		// back
		data[BACK].set(_1, data[RIGHT][_1]);
		data[BACK].set(_2, data[RIGHT][_2]);

		// right
		data[RIGHT].set(_1, tem);
		data[RIGHT].set(_2, tem2);

	}

	void B(void)
	{
		// back
		data[BACK].rotation(1);

		// top
		auto tem = data[TOP][_1];
		auto tem2 = data[TOP][_2];

		data[TOP].set(_1, data[RIGHT][_2]);
		data[TOP].set(_2, data[RIGHT][_4]);

		// right
		data[RIGHT].set(_2, data[BOTTOM][_4]);
		data[RIGHT].set(_4, data[BOTTOM][_3]);

		// bottom
		data[BOTTOM].set(_3, data[LEFT][_1]);
		data[BOTTOM].set(_4, data[LEFT][_3]);

		// LEFT
		data[LEFT].set(_1, tem2);
		data[LEFT].set(_3, tem);
	}

	void Bp(void)
	{
		
		// back
		data[BACK].rotation(-1);

		// top
		auto tem = data[TOP][_1];
		auto tem2 = data[TOP][_2];

		data[TOP].set(_1, data[LEFT][_3]);
		data[TOP].set(_2, data[LEFT][_1]);

		// LEFT
		data[LEFT].set(_1, data[BOTTOM][_3]);
		data[LEFT].set(_3, data[BOTTOM][_4]);

		// bottom
		data[BOTTOM].set(_3, data[RIGHT][_4]);
		data[BOTTOM].set(_4, data[RIGHT][_2]);

		// right
		data[RIGHT].set(_2, tem);
		data[RIGHT].set(_4, tem2);
	}

	void X(int n)
	{
		if (n == 0)
		{
			swap(data[FRONT], data[BACK]);
			swap(data[RIGHT], data[LEFT]);

			data[TOP].rotation(0);
			data[BOTTOM].rotation(0);

			return;
		}

		vector<int> order;
		int orien;

		switch (n)
		{
		case 1:
			order = { FRONT,LEFT,BACK,RIGHT };
			orien = 1;
			break;

		case -1:
			order = { FRONT,RIGHT,BACK,LEFT };
			orien = -1;
			break;

		default:
			cout << "X error" << endl;
			break;
		}

		auto tem = data[order[0]];
		data[order[0]] = data[order[1]];
		data[order[1]] = data[order[2]];
		data[order[2]] = data[order[3]];
		data[order[3]] = tem;

		// top
		data[TOP].rotation(orien * -1);

		// bottom
		data[BOTTOM].rotation(orien);
	}

	void Y(int n)
	{
		if (n == 0)
		{
			swap(data[FRONT], data[BACK]);
			swap(data[TOP], data[BOTTOM]);

			data[FRONT].rotation(0);
			data[BACK].rotation(0);

			data[RIGHT].rotation(0);
			data[LEFT].rotation(0);

			return;
		}

		vector<int> order;
		int orien;

		switch (n)
		{
		case 1:
			order = { TOP ,FRONT,BOTTOM,BACK };
			orien = -1;

			data[TOP].rotation(0);
			data[BACK].rotation(0);

			break;

		case -1:
			order = { TOP,BACK,BOTTOM,FRONT };

			data[BACK].rotation(0);
			data[BOTTOM].rotation(0);

			orien = 1;
			break;

		default:
			cout << "y error" << endl;
			break;
		}

		auto tem = data[order[0]];
		data[order[0]] = data[order[1]];
		data[order[1]] = data[order[2]];
		data[order[2]] = data[order[3]];
		data[order[3]] = tem;

		// right
		data[RIGHT].rotation(orien * -1);

		// left
		data[LEFT].rotation(orien);
	}

	void Z(int n)
	{
		if (n == 0)
		{
			swap(data[TOP], data[BOTTOM]);
			swap(data[RIGHT], data[LEFT]);

			for (int i = 0; i < 6; ++i)
				data[i].rotation(0);

			return;
		}

		vector<int> order;
		int orien;

		switch (n)
		{
		case 1:
			order = { TOP,LEFT,BOTTOM,RIGHT };

			for (auto &x : order)
				data[x].rotation(1);

			orien = -1;
			break;

		case -1:
			order = { TOP,RIGHT,BOTTOM,LEFT };
			orien = 1;

			for (auto &x : order)
				data[x].rotation(-1);

			break;

		default:
			cout << "Z error" << endl;
			break;
		}

		auto tem = data[order[0]];
		data[order[0]] = data[order[1]];
		data[order[1]] = data[order[2]];
		data[order[2]] = data[order[3]];
		data[order[3]] = tem;

		// front
		data[FRONT].rotation(orien * -1);

		// back
		data[BACK].rotation(orien);
	}
};


class CubePermutation
{
public:
	CubePermutation() : data(8), an(8)
	{
		vector<int> reserve_d{ 1,64,729,4096,15625,46656,117649,262144 };

		for (int i = 0; i < data.size(); ++i)
			data[i].reserve(reserve_d[i]);


		vector<int> reserve_a{ 1,20,80,300,800,3000,10000,45000, 120000 };
		
		for (int i = 0; i < data.size(); ++i)
			an[i].reserve(reserve_a[i]);

		mp.reserve(1000000);
		
		cal_ans();
	}

	void set(const vector<string> &input)
	{
		for (auto &x : data)
			x.clear();

		data[0].push_back(Cube{ input });
	}

	int run()
	{
		return permutate_data();
	}

private:
	enum { L = 1, Lp, U, Up, B, Bp };

	vector<vector<Cube>> data;
	vector<vector<Cube>> an;
	unordered_multimap<Cube::Type, Cube&> mp;

	int permutate_data(void)
	{
		int now, pre;
		int i, k;
		int t = check_ans(0, 0);

		if (t != -1)
			return t;

		for (now = 1; now <= 7; ++now)
		{
			pre = now - 1;

			for (i = 0; i < data[pre].size(); ++i)
			{
				for (k = 1; k <= 6; ++k)
				{
					if (is_redundant(data, pre, i, k))
						continue;


					data[now].emplace_back(data[pre][i].flip_cp(k));

					t = check_ans(now, data[now].size() - 1);

					if (t != -1)
					{
						return now + 7;
					}
				}
			}
		}

		return 99;
	}

	void permutate_ans(void)
	{
		int now, pre;
		int i, k;
		

		for (now = 1; now <= 7; ++now)
		{
			pre = now - 1;

			for (i = 0; i < an[pre].size(); ++i)
			{
				if (i == 121 && now == 7)
					i = 121;

				for (k = 1; k <= 6; ++k)
				{
					if (is_redundant(an, pre, i, k))
						continue;

					an[now].emplace_back(an[pre][i].flip_cp(k));

					check_map(now, an[now].size() - 1);
				}
			}
		}
	}

	bool is_redundant(vector<vector<Cube>> &cdata, int pre, int idx, int now_step) const
	{
		int last_step = cdata[pre][idx].get_last_path();
		int m, M;

		if (now_step == last_step && ((last_step == Lp) || (last_step == Up) || (last_step == Bp)))
			return true;

		if (now_step == last_step && cdata[pre][idx].get_repeat_cnt() == 2)
			return true;

		if (last_step < now_step)
		{
			m = last_step;
			M = now_step;
		}
		else
		{
			m = now_step;
			M = last_step;
		}

		if (M - m == 1 && (m & 0x01))
			return true;

		return false;
	}

	int check_ans(int now, int idx) const
	{
		auto key = data[now][idx].hash();

		auto range = mp.equal_range(key);

		bool found = false;

		for (auto itr = range.first; itr != mp.end() && itr != range.second; ++itr)
			if (itr->second == data[now][idx])
				return itr->second.get_step();

		return -1;
	}

	void cal_ans(void)
	{
		an[0].push_back(Cube{});
		mp.emplace(an[0][0].hash(), an[0][0]);

		permutate_ans();
	}

	void check_map(int now, int idx)
	{
		auto key = an[now][idx].hash();

		auto range = mp.equal_range(key);

		bool found = false;

		for (auto itr = range.first; itr != mp.end() && itr != range.second; ++itr)
			if (itr->second == an[now][idx])
			{
				found = true;
				break;
			}

		if (found)
			an[now].pop_back();
		else
			mp.emplace(key, an[now][idx]);
	}
};


int main(void)
{
	vector<string> input(6);

	CubePermutation p;

	int n = 9999;

	cin >> n;

	cin.get();
	cin.get();

	while (n--)
	{
		for (int i = 0; i < 6; ++i)
			getline(cin, input[i]);

		p.set(input);

		auto step = p.run();

		cout << step << endl;

		getline(cin, input[0]);
	}
	
	return 0;
}

稍微解說

class Face

是紀錄面的資訊，由於一面有 4 格，每格可能會有 6 種可能的顏色
所以用 4 bits 就可以紀錄 6 種顏色，總共需要 4 x 4 = 16 bits，因此我用 uint_16

rotation() method :
單面旋轉的函式，0 代表旋轉 180 度，1 代表順時針轉 90 度，-1 代表逆時針轉 90 度

class Cube

是紀錄方塊的資訊，有 6 面，所以我用 6 個 class Face 去紀錄

set_position()、rotation()、set_corner():
這三個 methods 是在把方塊對其基準點歸位

L()、Lp()、…、X()、Y()、Z() :
就是最一開始講的那幾個操作

flip()、flip_cp() :
轉動方塊的面

repeat_cnt : 用來檢查同樣的操作做了幾次
last_step : 紀錄最後一次的操作是甚麼
step_cnt : 代表從列舉起始狀態開始走了幾步，也就是 step k 的 k

class CubePermutation

an : 用來列舉還原狀態方塊的 step 0 ~ step 7
data : 用來列舉題目給的待解狀態方塊 step 0 ~ step 7
mp : Hash Table，存的是 an 的方塊 hash value 和方塊資訊

注意在建構式的時候，我就已經 reserve an 的 capacity 了，為的就是讓 vector 不要在重新 allocte memory
這樣會改變 Cubes 的記憶體位置，造成 mp 中存的 reference 存取錯誤，注意這是不好的作法，我只是求方便

cal_ans()、permutate_ans()、check_map() : 用來列舉 an 的

permutate_data()、check_ans() : 用來列舉題目給的待解狀態 data

is_redundant() : 用來檢查 3 規則

set() : 新的輸入就要做一些清空的動作