ACM-雙向BFS之魔闆——求助ING！ 魔闆

time limit: 10000/5000 ms (java/others)    memory limit: 65536/32768 k (java/others)

total submission(s): 1675    accepted submission(s): 353

problem description

在魔方風靡全球之後不久，rubik先生發明了它的簡化版——魔闆。魔闆由8個同樣大小的方塊組成，每個方塊顔色均不相同，可用數字1-8分别表示。任一時刻魔闆的狀态可用方塊的顔色序清單示：從魔闆的左上角開始，按順時針方向依次寫下各方塊的顔色代号，所得到的數字序列即可表示此時魔闆的狀态。例如，序列(1,2,3,4,5,6,7,8)表示魔闆狀态為：

1 2 3 4

8 7 6 5

對于魔闆，可施加三種不同的操作，具體操作方法如下：

a: 上下兩行互換,如上圖可變換為狀态87654321

b: 每行同時循環右移一格,如上圖可變換為41236785

c: 中間4個方塊順時針旋轉一格,如上圖可變換為17245368

給你魔闆的初始狀态與目标狀态，請給出由初态到目态變換數最少的變換步驟，若有多種變換方案則取字典序最小的那種。

input

每組測試資料包括兩行，分别代表魔闆的初态與目态。

output

對每組測試資料輸出滿足題意的變換步驟。

sample input

sample output

題目：

這道題，bfs會逾時，于是我用的雙向bfs。。。

這題目中的vis要用到 康托展開（詳情可戳   ）

我的思路：

因為字典序，是以按照a->b->c搜尋。

q隊列存正向搜尋的，搜尋過的置1，p隊列存反向搜尋的，搜尋過的置2。（初始化為0）

每次都擴充一層結點。

輸出的時候先輸出 正向的答案  再反向 輸出反向的答案。

vis數組記憶體到達該點時的節點和标記（1或者2）

網上說用預處理來做，

但是我試了試發現雙廣不會逾時，就是wa。。。快被虐呆了~~o(>_<)o ~~

求大神大牛們幫忙看一下。。。